Меню сайта

Категории раздела
Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) [36]
Решение олимпиадных задач по программированию
Готовимся к олимпиаде по математике [3]
Решение олимпиадных задач по математике

Мини-чат

Наш опрос
Уважаемый посетитель сайта, к какой категории вы себя относите?
Всего ответов: 5512

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Главная

Регистрация

Вход
Вы вошли как Гость | Группа "Гости" | RSS


Личный сайт учителя математики и информатики

Фоновой Натальи Леонидовны



Пятница, 14.08.2020, 08:49
Главная » Файлы » Внеурочная деятельность » Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru)

Счастливые билеты 2
13.02.2012, 09:08

Условие:
Необходимо посчитать количество "счастливых" билетов с заданной суммой цифр, среди тех, номер которых состоит из 2*N разрядов. "Счастливым" является билет, у которого сумма первых N цифр равна сумме N последних цифр.

Технические условия:
Во входном файле находятся два числа разделенных пробелом: первое - N (1<=N<=50); второе - сумма цифр интересующих нас билетов (неотрицательное число не превосходящее 1000).
В качестве ответа необходимо вывести найденное число "счастливых" билетов.

Примеры входных и выходных файлов:
Input.txt
2 2
Output.txt
4

Условию удовлетворяют билеты: 0101, 0110, 1001, 1010.

Решение:
{by Boris Bukh <brbukh@yahoo.com>}

--------------- cut ----------------
Можно вывести формулу для V[i,j] из рекуррентности. Обозначим через
F[i] обыкновенную производящую функцию для V[i,j] при фиксированном i.
Тогда F[0]=1, F[i]=F[i-1]*(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9) =>
=>F[i]=((1-x^10)/(1-x))^i=sum(x^10k*C_ik*(-1)^(i-k))*(-1)^i/(1-x)^i,
где C_ik - это биномиальный коэффициент.
Это дает нам еще один алгоритм. Мы можем вычислить левый множитель с
помощью хорошо известного алгоритма вычисления биномиальных
коэффициентов, а потом мы можем вычислить частичные суммы i раз. Этот
алгоритм чуть быстрее, но не намного. Он работает за время
(N^2/2+N*S)*(арифметика).
--------------- cut ----------------

{$N+}
var N,S:LongInt;
{ V[i,j] - number of i-digit numbers having sum of digits=j
Recurrence: V[0,j]=delta_0j
V[i,j]=sum(k=0..9,V[i-1,j-k])
implies
V[i,j]-V[i,j-1]=V[i-1,j]-V[i-1,j-10]
Observation: V[i] is a function of V[i-1] only.
We don't need to store V[i-1]. }
V:array[0..1,-10..1000]of Comp; { we store only two consecutive rows }
i,j,k:Integer; sel:Integer;
begin
Assign(Input,'input.txt');Reset(Input);
Assign(Output,'output.txt');Rewrite(Output);
Read(N,S);
if (S and 1)<>0 then { S has to be even }
begin
WriteLn(0);Exit;
end;
S:=S div 2;
FillChar(V,SizeOf(V),0);
sel:=0; V[sel,0]:=1;
for i:=1 to N do
begin
FillChar(V[sel xor 1],SizeOf(V) div 2,0);
for j:=0 to S do { We have to do calculations up to S only }
V[sel xor 1,j]:=V[sel xor 1,j-1]+V[sel,j]-V[sel,j-10];
sel:=sel xor 1;
end;
WriteLn(V[sel,S]*V[sel,S]:0:0);
end.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 1132 | Загрузок: 0 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Кнопка сайта

Одна кнопка

время жизни сайта

Сайт участвует
конкурс сайтов 

Новости образовани

Фраза дня

Web-мастеру

OperaFirefoxGoogle ChromeDownload Master
QIPSkypeµTorrentTeamViewer
Dr.Web CureITAvira AntiVirTotal CommanderCDBurnerXP
PicasaIrfanViewCheMaxDAEMON Tools
AIMPKMPlayerBSplayerK-Lite Codec Pack

Установить себе такой Блок
Скрипты и HTML для uCOz

Раскрутка сайта
Graffiti Decorations(R) Studio (TM) Site Promoter

Copyright MyCorp © 2020
/td>