#203

Мячик на лесенке

Темы: [Динамическое программирование: один параметр] [Рекуррентные последовательности]

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.

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

Вводится одно число 0 < N < 31.

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

Выведите одно число — количество маршрутов.

Примеры

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

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

#204

НОП

Темы: [Динамическое программирование: последовательности]

Даны две последовательности, требуется найти длину их наибольшей общей подпоследовательности.

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

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

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

Требуется вывести одно число – длину наибольшей общей подпоследовательности двух данных последовательностей или 0, если такой подпоследовательности нет.

Примеры

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

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

#205

НВП

Темы: [Динамическое программирование: последовательности]

Дана последовательность, требуется найти длину её наибольшей возрастающей подпоследовательности. Подпоследовательностью последовательности называется некоторый набор её элементов, не обязательно стоящих подряд.

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

В первой строке входных данных задано число N - длина последовательности (1 ≤ N ≤ 1000). Во второй строке задается сама последовательность (разделитель - пробел). Элементы последовательности - целые числа, не превосходящие 10000 по модулю.

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

Требуется вывести длину наибольшей строго возрастающей подпоследовательности.

Примеры

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

6
3 29 5 5 28 6

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

#206

Обход таблицы

Темы: [Динамическое программирование на таблицах]

В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку.

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

Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).

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

Выведите искомое количество способов.

Примечание

При указанных ограничениях число способов входит в тип Longint.

Примеры

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

1 10

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

#207

Последовательность из 0 и 1

Темы: [Динамическое программирование: один параметр] ["Длинная" арифметика]

Требуется подсчитать количество последовательностей длины \(N\), состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

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

На вход программы поступает целое число \(N\) (\(1\le N\le100\)).

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

Выведите количество искомых последовательностей.

Примеры

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

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