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

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + 1 (n>0),
a_2n+2 = a_2n+1 - a_n (n>0),
a₀=1, a₁=1.

Входные данные
Вводится натуральное число n, не превосходящее 1000.

Выходные данные
Выведите ответ к задаче.

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + a_n-1,
a_2n+1 = a_n – a_n-1,
a₀ = a₁ = 1.

Входные данные
Вводится одно натуральное число n (1≤n≤1000).

Выходные данные
Вывести одно число a_n.

Последовательность чисел Фибоначчи определяется следующим образом: F₀ = F₁ = 1,

F_n+1 = F_n+F_n-1. Напишите программу для вычисления последней цифры n-го члена последовательности.

Входные данные
В единственной строке входных данных записано натуральное число n (1≤n≤1000).

Выходные данные
Вывести последнюю цифру числа F_n.

Компания, занимающаяся железнодорожными перевозками, получила заказ сформировать поезд, состоящий из определённого числа вагонов. Проблема в том, что у компании есть вагоны, выпущенные в разное время, так что каждый из вагонов может иметь один из двух видов сцеплений на каждом конце. У компании также есть один локомотив.

Сцепления и для локомотива, и для вагонов обозначены буквой A или B. Повернуть вагон или локомотив противоположной стороной невозможно.

Дана информация о вагонах и локомотиве. Требуется найти число способов сформировать разные поезда заданной длины из имеющихся видов вагонов. Дополнительным требованием является то, что тип сцеплений на каждом конце состава должен соответствовать типу сцеплений локомотива.

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

Пример 1. Пусть у компании есть вагоны AA, AA, AB, BA, BA и локомотив AB. В поезде должно быть 4 вагона. Из данных вагонов можно сформировать только два различных поезда: BAAAABBA и BAABBAAA. Локомотив можно присоединить к поезду как с левого (используя сцепление B), так и с правого конца (используя сцепление A).

Пример 2. Пусть у компании есть только по одному вагону каждого типа (AA, AB, BA, BB) и локомотив AA, а поезд должен состоять из трёх вагонов. Существует три способа сформировать поезд: AAABBA, ABBAAA и ABBBBA.

Входные данные
В первой строке через пробел N - число вагонов, находящихся в распоряжении компании, и K - требуемая длина поезда в вагонах. Вторая строка описывает тип сцеплений локомотива. Следующие N строк описывают типы сцеплений вагонов. Описания даны как AB, AA, BB или BA.

Ограничения: 1 <= K <= N <= 40.

Выходные данные
В первой строке выводится слово "YES", если можно сформировать хотя бы один поезд, или "NO" - в противном случае.

Если поезд сформировать возможно, во второй строке должно указываться число способов это сделать.

{F_k} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи F_k = F_k - 1 + F_k - 2 (для любого целого k). Даны i, F_i, j, F_j, n (i <> j). Найти F_n. Пример части последовательности:

k	-2	-1	0	1	2	3	4	5	6
Fk	-5	4	-1	3	2	5	7	12	19

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= F_k <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Входные данные
В первой строке находятся числа i, F_i, j, F_j, n.

Выходные данные
Вывести одно число F_n.

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

Цель игры - убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки

10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000.

Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:

1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150.

Входные данные
В первой строке находится число карт N, во второй - разделённые пробелами N чисел на картах.

Ограничения: 3 <= N <= 100, числа на картах целые от 1 до 100.

Выходные данные
Вывести одно целое число - минимально возможное число очков.

Каждый член последовательности десятичных цифр d¹, d², d³..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d¹, d², d³ найти N-й член последовательности.

Ограничения: 1 <= N <= 10¹⁵.

Входные данные
В первой строке находятся цифры d₁, d₂, d₃, разделённые пробелами, во второй - число N.

Выходные данные
Вывести одну цифру - d_N.

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.

Ограничения: 1 <= N <= 60.

Входные данные
В первой строке записано слово S.

Выходные данные
Вывести одно целое число - количество способов вычёркивания.

В последовательности чисел a₁, a₂, a₃, ... задан первый член, а остальные вычисляются по формуле a_i = (a_i - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a₁ < 10 000, 1 <= N <= 2 000 000 000.

Входные данные
В первой строке находятся числа a₁ и N, разделённые пробелом.

Выходные данные
Вывести одно число - a_N.

Строку Фибоначчи F(K) для натуральных чисел K определим так: F(1) = 'A', F(2) = 'B', F(K) = F(K - 1) + F(K - 2) при K > 2, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).

Ограничения: длина S от 1 до 25, 1 <= N <= 45.

Примечание. Длина F(45) равна 1 134 903 170.

Входные данные
В первой строке содержится число N, во второй - строка S.

Выходные данные
Выводится одно число - количество вхождений строки S в строку Фибоначчи F(N).

Кубик, грани которого помечены цифрами от 1 до 6, бросают N раз. Найти вероятность того, что сумма выпавших чисел будет равна Q.

Ограничения: 1 <= N <= 500, 1 <= Q <= 3000.

Входные данные
В первой строке находятся числа N и Q через пробел.

Выходные данные
Выводится единственное вещественное число, которое должно отличаться от истинного значения не более чем на 0.01 истинного значения.

Сообщения SMS сотового телефона MOBILA составлены из прописных латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая - нужно нажать кнопку дважды и т.д. Так, чтобы набрать слово "SMS", нужно нажать

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

Чтобы ввести две буквы, находящиеся на одной кнопке, нужно между нажатиями клавиши сделать паузу. Например, чтобы ввести сообщение "AA", нужно нажать

(ABC)(пауза)(ABC)

Если на кнопке три буквы, то, как только такая кнопка нажата три раза, последняя буква добавляется в сообщение немедленно, а следующие нажатия той же кнопки относятся к следующей букве сообщения. Аналогично, если на кнопке четыре буквы, то после четырёх нажатий в сообщение будет добавлена последняя буква. То есть последовательность нажатий

(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)

соответствует сообщению "CAA". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.



Входные данные
В первой строке задана длина оригинального сообщения N. Вторая строка содержит полученное SMS-сообщение. 1 <= N <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв.

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

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Входные данные
В первой строке содержится последовательность цифр. Цифр не более 100.

Выходные данные
Вывести одно число.

Дано N целых чисел A₁, A₂, ..., A_N. Требуется найти количество различных значений сумм вида k₁A₁ + k₂A₂ + ... + k_NA_N.
(1 <= N <= 500, 0 <= Ai <= 100, 0 <= k_i <= 1, все числа целые.)

Входные данные:
В первой строке находится число N, во второй - A₁, A₂, ..., A_N через пробел.

Выходные данные: 
Вывести одно число - количество различных значений сумм.

Дана матрица N*N, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной K (клетку можно посещать несколько раз).

Входные данные
В первой строке находятся разделенные пробелом числа N и K. Затем идут N строк по N чисел в каждой. 2 <= N <= 100, элементы матрицы имеют значения от 1 до 9999, 1 <= K <= 2000, все числа целые.

Выходные данные
Вывести одно число - максимальную сумму.

N  гангстеров собираются в ресторан. i-й гангстер приходит в момент времени T и имеет богатство P_i. Дверь ресторана имеет K + 1 степень открытости, они обозначаются целыми числами из интервала [0, K]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте S_i. Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, T]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.

Входные данные
В первой строке находятся числа N, K, T, во второй - T₁, T₂, ..., T_N, в третьей - P₁, P₂, ..., P_N. в четвёртой - S₁, S₂, ..., S_N. Числа в строках разделены пробелами. 1 <= N <= 100, 1 <= K <= 100, 1 <= T <= 30 000, 0 <= T_i <= T, 1 <= P_i <= 300, 1 <= S_i <= K, все числа целые.

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

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

Входные данные
В первой строке находится число N. В следующих N строках содержатся по N цифр без пробелов. 2 <= N <= 250.

Выходные данные
Выводятся N строк по N символов. Символ решётка показывает, что маршрут проходит через эту клетку, а минус - что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.

Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял, что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.

Недавно он получил по электронной почте фотографию места преступления. Подозрительный фрагмент (тот, на котором изображен предмет, похожий на шахматную доску) уже был скопирован в отдельный файл, но вдруг выяснилось, что, поскольку фотография была сжата с потерей качества, некоторые пиксели на ней из белых или черных стали серыми. Таким образом, определение того, является ли сфотографированный предмет шахматной доской, стало намного более сложным.

Все усложняется тем, что на фотографию могла попасть не вся шахматная доска, а лишь ее часть. Например, на приведенном рисунке на фотографию попала часть доски, у которой каждое поле имеет длину стороны, равную трем пикселям.

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

Шахматная доска — это квадрат, разбитый на \(x^2\) (для некоторого \(x\)) равных квадратов — полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет — черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.

Формат входных данных
Первая строка содержит два целых числа: \(m\) и \(n\) — размеры фрагмента фотографии в пикселях (\(1 \le m, n \le 250\)).

Следующие \(m\) строк содержат по \(n\) символов каждая, \(j\)-й символ \(i\)-й строки соответствует пикселю с координатами \((i, j)\). Символ <<.>> (точка) означает белый пиксель, символ <<*>> — черный, символ <<?>> — серый.

Формат выходных данных
Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите слово <<YES>>. После этого выведите \(m\) строк по \(n\) символов в каждой. Они должны содержать изображение соответствующей части шахматной доски в том же формате, что и во входных данных, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое.

В противном случае выведите слово <<NO>>.

На окружности отметили N точек и пронумеровали их последовательно числами от 1 до N. Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами i и j.

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

Входные данные
Вводятся три натуральных числа N, i, j (2 ≤ N ≤ 2 000, 1 ≤ i < j ≤ N).

Выходные данные
Требуется вывести остаток от деления количества ломаных на 10⁹.

Крупная межгалактическая сеть мебельных магазинов Galactic-Мебель недавно вышла на рынок мебели для кухонь в звездной системе LoST-2007. В этой звездной системе во всех квартирах кухни имеют форму прямоугольника размером a на b метров. При этом вдоль одной из стен принято ставить стол, в смежной с ней стене находится окно. Таким образом, для размещения различных кухонных шкафчиков остается угол со сторонами a и b метров.

Для экономии места в этой звездной системе принято ставить шкафчики вплотную друг к другу и к углу кухни. Кроме этого, сами шкафчики встраиваются внутрь стены, то есть вдоль стены расположены только их дверцы.

В звездной системе LoST-2007 используется n типов кухонных шкафчиков. Каждый тип шкафчиков характеризуется своей шириной wi, при этом на кухне должен присутствовать ровно один экземпляр каждого типа шкафчиков.

Недавно директор маркетингового отдела Galactic-Мебель заметил, что он может предложить клиентам несколько вариантов расположения шкафчиков на кухне. Различными считаются варианты, которые отличаются расположением хотя бы одного шкафчика. При этом шкафчики различных типов могут иметь одинаковую ширину, однако отличаются внешней отделкой. Так что даже размещения, которые отличаются лишь позициями шкафчиков с равной шириной, считаются различными. Например, пусть a = 3, b = 4 и есть два типа шкафчиков, шириной 1 и 2, соответственно.


Тогда возможно шесть планировок кухни. Возможные планировки показаны на рисунке.

Требуется по заданным размерам кухни и шкафчиков найти число различных планировок.

Входные данные
Первая строка содержит три целых числа: a, b и n (1 ≤ a ≤ 300, 1 ≤ b ≤ 300, 1 ≤ n ≤ 100). Каждая из следующих n строк содержит целое число w_i (1 ≤ w_i ≤ 300) — ширину соответствующего шкафчика.

Выходные данные
Выведите количество различных планировок кухни.