Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Февраль 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
28.02.2002
00:18:54
23:38:21


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Служба Рассылок Subscribe.Ru
Олимпиадные задачи c решениями на Turbo Pascal

Олимпиадные задачи с решениями на Turbo Pascal

Рассылка проекта Sapisoft.By.Ru [#016]

Подписчиков на 20.02.2002 - 2637 человек.
Главная Программы Задачи Рассылки Гостевая книга Контакты

Здравствуйте!
  Прошу прощения за небольшой перерыв в работе рассылки, связанный с проблемами на АТС. По традиции;) представляем ещё одно решение задачи из прошлого номера.

Счастливые билеты 2 (3 уровень)

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

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

Пример файлов входных и выходных данных:

Input.txt

Output.txt
2 2 4

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

Решение: (by Boris Bukh <brbukh@yahoo.com>)
{$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.

--------------- 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 ----------------

--------------- cut ----------------
Ещё один алгоритм от Hellman'a (alexec@newmail.ru):

Нужно научиться раскладывать данное число (половину требуемой суммы) на N слагаемых, каждое из которых находится в интервале от 0 до 9. Дальше есть два пути:
1. Алгоритм может сгенерировать абсолютно все разложения (порядок слагаемых имеет значение). Тогда мы просто считаем их количество.
2. Алгоритм генерирует все разложения, которые нельзя получить друг из друга путем перестановок слагаемых. Тогда при нахождении очередного разложения надо увеличивать счетчик не на единицу, а на
N!
---------------
k0!*k1!*...*k9!
где k0, k1, ..., k9 - количество повторяющихся чисел в разложении.
Например, для такого разложения
1+2+2+3+3+3+3+8
получим
8!
----- = 840
2!*4!
Независимо от выбранного алгоритма в конце число надо возвести в квадрат, т.к. мы посчитали только количество возможных вариантов половинки билета. Билет же целиком может состоять из любой комбинации двух таких половинок.
--------------- cut ----------------
Реклама в рассылке:

RLE Banner Network    

  

Рассылки проекта Sapisoft:
Новости проекта Sapisoft [Шамис Алексей]
Информация о выходе новых версий программ и прочих обновлениях на сайте.

 Уроки программирования на Turbo Pascal [Галин Павел]
Хотите стать Великим Программистом? Начните свой путь к вершине славы с изучения языка Turbo Pascal. Он как нельзя лучше подходит для начинающих программистов и в то же время используется для разработки сложных "профессиональных" программ.

 Олимпиадные задачи с решениями на Turbo Pascal [Шамис Алексей]
В рассылке публикуются решения интересных олимпиадных задач различного уровня. Периодичность - 2-3 раза в неделю. Каждый выпуск содержит решение 2-3 задач с подробным анализом описанием алгоритма решения.

 Задача в неделю. Олимпиадные задачи по информатике [Алексеев Александр]
Каждый понедельник в рассылке публикуется задача, которую необходимо решить и в следующий понедельник прислать программу на тестирование. Решения проверяются и в пятницу публикуется разбор и итоги тестирования.

Всегда рады видеть Вас на нашем сайте. Жду ваших предложений и замечаний, Шамис Алексей

Copyright © 2001-2002 by Shamis Alex.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное