Олимпиадная информатика

Задача «Взрывоопасность»

2 секунды и 64 Мб памяти

На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются отходы двух типов: типа А - особо опасные и типа В - неопасные. Все отходы упаковываются в прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в штабель (один над другим) для захоронения.

Штабель является взрывоопасным, если в нём подряд идут не менее, чем К контейнеров с отходами типа А. Вам нужно подсчитать количество возможных вариантов формирования одного взрывоопасного штабеля, состоящего из N контейнеров.

Формат входного файла input.txt Входной файл содержит два разделенных пробелом целых числа N и K(1<N<60и 1<K<N).

Формат выходного файла output.txt Выходной файл содержит одно число - количество вариантов формирования взрывоопасных штабелей.

program aa;
 var x:int64;a:array[0..62]of int64;j,i,n,k,z:longint;
begin
 assign(input,'input.txt');reset(input);
 assign(output,'output.txt');rewrite(output);
  read(n,k);
  a[0]:=1;
  for i:=1 to n do
  begin
   x:=0;
   for z:=0 to k-1 do
   x:=x+a[z];
   a[k]:=a[k]+a[k]+a[k-1];
   for z:=k-1 downto 1  do
   a[z]:=a[z-1];
   a[0]:=x;
  end;
  write(a[k]);
 close(input);close(output);
end





close
 

Разбор задачи №5 "Взрывоопасность"

Задачу можно решить методом динамического программирования. Заведём массив из К+1 элемента. При i<К в i-том элементе массива будем хранить число вариантов построения безопасного штабеля, в котором сверху лежит слой из i опасных контейнеров при достигнутой высоте, а в элементе с индексом К - число вариантов опасных штабелей такой высоты.

При увеличении высоты на 1 можно положить сверху как опасный, так и неопасный контейнер. Если добавлен неопасный контейнер, то число вариантов опасных будет останется прежним, а число вариантов с нулевым слоем наверху будет равно сумме всех с индексами от 0 до К-1 (a[0]:=a[0]+a[1]+…+a[k-1]). Если сверху добавили опасный контейнер, то число опасных вариантов будет равно числу вариантов опасных + число вариантов с индексом К-1 - они тоже перейдут в опасные( таким образом в итоге имеем a[k]:=a[k]+a[k]+a[k-1]). Число вариантов с индексами от 1 до К-1 станет равным числу вариантов с индексом на 1 меньше. ( a[i]:=a[i-1]).

В самом начале нет ни одного штабеля, поэтому только a[0]=1, все остальные - элементы - нули. Проведём описанную процедуру в цикле от 1 до N и получим ответ - значение a[k]. При граничных входных данных 60 и 1 число вариантов равно количеству двоичных 60-значных чисел (с ведущими нулями) содержащих хотя бы одну 1, т. е. 260 -1, поэтому нужно использовать 64-битные переменные (тип int64 в Паскале) или "длинную" арифметику.