Реферат: Динамическое программирование

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры, последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более двух контейнеров типа A. Для заданного количества контейнеров N определить число безопасных стопок.

Формат входных данных

Одно число 0<N<31.

Формат выходных данных

Одно число — количество безопасных вариантов формирования стопки.

К-ичные числа

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.

Ограничения: 2<=K<=10, N + K<=18.

Формат входных данных

Числа N и K в десятичной записи, разделенные пробелом или переводом строки.

Формат выходных данных

Искомое число в десятичной записи.

Подпалиндром

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины.

Формат входных данных

Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.

Формат выходных данных

В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.

Паровозики

N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью.

Написать программу, определяющую, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов.

Формат входных данных

Два числа — 0 < N < 17 и 0 < p < N + 1.

Формат выходных данных

Одно число — s.

Плитки

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1 * 1. Он выбирает ровно Nплиток и выкладывает их в полоску. Например, при N=10 она может выглядеть следующим образом:

(буквой К обозначена красная плитка, С — синяя, З — зеленая).

После этого Петя заполняет следующую таблицу: