007. Коридор

(Время - 1 сек., память - 16 Мб)

Прямоугольный коридор длиной N метров и шириной M метров решили застелить N прямоугольными плитками шириной 1 метр и длиной M метров, таким образом, чтобы не было не застеленной поверхности.

Требуется написать программу, которая найдет количество способов это сделать. Например, для коридора с размерами 6 на 4 существует четыре способа застелить плитками 1 на 4.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Входные данные

В единственной строке входного файла input.txt записаны два целых числа – M (длина плитки и ширина коридора) и N (длина коридора). Для этих чисел верны неравенства 2  M  N  50.

Выходные данные

В единственную строку выходного файла output.txt нужно вывести одно число – количество способов.

Примеры

input.txt

output.txt

1

4 6

4

2

2 2

2

Разбор

Задача решается методом динамического программирования. Для этого обозначим через A(n) – количество способов замостить коридор длиной n. Так как для коридора длиной k<m плитки можно укладывать только горизонтально, то A(k)=1. В других случаях плитки в последнем ряду можно положить или горизонтально или вертикально, а тогда A(n)=A(n‑1)+A(n‑m). Приведенные соотношения позволяют последовательно рассчитать требуемое количество замощений кридора. Ответом будет значение A(N).

Программа на Паскале

{Автор программы - А.В.Алексеев,  дата написания - 23.04.2012}

var

  m, n, i : integer;

  a : array [0..50] of int64;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(m,n);

  for i:=0 to m-1 do a[i]:=1;

  for i:=m to n do

    a[i]:=a[i-1]+a[i-m];

  write(a[n])

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2007-2008 уч. год, 3-й тур

Тематика

Динамическое программирование

Примерная сложность

38%

Ссылки в Интернете

Условие , сдача решения – http://acmu.ru/index.asp?main=task&id_task=320

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 26.04.2012