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

A. Кузнечик собирает монеты

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до $n$. В начале Кузнечик сидит на столбике с номером 1 и хочет добраться до столбика с номером $n$. Он может прыгнуть вперед на расстояние от 1 до $k$ столбиков, считая от текущего.

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

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

В первой строке вводятся два натуральных числа: $n$ и $k$ $(3 ⩽ n ⩽ 10\ 000, 1 ⩽ k ⩽ 10\ 000)$, разделённые пробелом. Во второй строке записаны через пробел $n − 2$ целых числа – количество монет, которое Кузнечик получает на каждом столбике, от $2$-го до $n − 1$-го. Если это число отрицательное, Кузнечик теряет монеты. Гарантируется, что все числа по модулю не превосходят $10\ 000$.

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

В первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик. Во второй строке выводится число прыжков Кузнечика, а в третьей строке – номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).

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

Пример

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

5 3
2 -3 5

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

7
3
1 2 4 5

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

10 3
-13 -2 -14 -124 -9 -6 -5 -7

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

-16
4
1 3 6 8 10

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

12 5
-5 -4 -3 -2 -1 1 2 3 4 5

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

14
7
1 6 7 8 9 10 11 12

Решение

B. Черепаха и монеты

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Черепаха хочет переползти из левого верхнего угла поля размером $n$ на $m$ клеток $(2 ⩽ n,m ⩽ 1000)$ в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Кроме того, проходя через каждую клетку, Черепаха получает (или теряет) несколько золотых монет (это число известно для каждой клетки).

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

В первой строке вводятся два натуральных числа: $n$ и $m$ $(2 ⩽ n,m ⩽ 1000)$, разделённые пробелом. В каждой из следующих $n$ строк записаны через пробел по $m$ чисел $a_{ij}$ $(|a_{ij}| ⩽ 10)$, которые обозначают количество монет, получаемых Черепашкой при проходе через каждую клетку. Если это число отрицательное, Черепашка теряет монеты.

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

В первой строке программа должна вывести наибольшее количество монет, которое может собрать Черепаха. Во второй строке без пробелов выводятся команды, которые нужно выполнить Черепахе: буква R (от слова right) обозначает шаг вправо, а буква D (от слова down) — шаг вниз.

Пример

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

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

6
RRDD

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

4 5
4 5 3 2 9
4 6 7 5 9
5 2 5 -3 -10
3 5 2 9 3

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

41
RDRDDRR

Решение

C. Наибольшая возрастающая подпоследовательность

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Пусть $a_1, a_2, …, a_n$ — числовая последовательность. Длина последовательности — это количество элементов этой последовательности. Последовательность $a_{i_1}, a_{i_2}, …, a_{i_k}$ называется подпоследовательностью последовательности $a$, если $1 ⩽ i_1 < i_2 < … < i_k ⩽ n$. Последовательность $a$ называется возрастающей, если $a_1 < a_2 < … < a_n$.

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

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

В первой строке задано одно число $n$ $(1 ⩽ n ⩽ 2000)$ — длина подпоследовательности. В следующей строке задано $n$ целых чисел $a_i$ $(-10^9 ⩽ a_i ⩽ 10^9)$ — элементы последовательности.

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

В первой строке выведите число $k$ — длину наибольшей возрастающей подпоследовательности. В следующей строке выведите $k$ чисел — саму подпоследовательность.

Пример

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

8
1 4 1 5 3 3 4 2

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

3
1 4 5

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

3
1 2 3

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

3
1 2 3

Решение

D. Ход конем

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 256 мегабайт

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Напишите программу, определяющую количество телефонных номеров длины $n$, набираемых ходом коня. Поскольку таких номеров может быть очень много, выведите ответ по модулю $10^9$.

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

Во входном файле записано целое число $n$ $(1 ⩽ n ⩽ 100)$.

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

Выведите в выходной файл искомое количество телефонных номеров по модулю $10^9$.

Пример

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

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

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

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

Решение

E. Расстояние по Левенштейну

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Дана текстовая строка. С ней можно выполнять следующие операции:

Заменить один символ строки на другой символ.
Удалить один произвольный символ.
Вставить произвольный символ в произвольное место строки.

Например, при помощи первой операции из строки «СОК» можно получить строку «СУК», при помощи второй операции — строку «ОК», при помощи третьей операции — строку «СТОК».

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

Определите расстояние Левенштейна для двух данных строк.

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

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

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

Требуется вывести одно число — расстояние Левенштейна для данных строк.

Пример

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

ABCDEFGH
ACDEXGIH

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

Решение

F. Кафе

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 64 мегабайта

Около Петиного университета недавно открылось новое кафе, в котором действует следующая система скидок: при каждой покупке более чем на 100 рублей покупатель получает купон, дающий право на один бесплатный обед (при покупке на сумму 100 рублей и меньше такой купон покупатель не получает).

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

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

В первой строке входного файла записано целое число $n$ $(0 ⩽ n ⩽ 100)$. В каждой из последующих $n$ строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.

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

В первой строке выдайте минимальную возможную суммарную стоимость обедов. Во второй строке выдайте два числа $k_1$ и $k_2$ — количество купонов, которые останутся неиспользованными у Пети после этих $n$ дней и количество использованных им купонов соответственно.

В последующих $k_2$ строках выдайте в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выдайте то из них, в котором значение $k_1$ максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.

Пример

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

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

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

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

220
1 1
2

Решение

G. Удаление скобок 2.0

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

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

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

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

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

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

Пример

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

([)]

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

[]

Решение

H. Продавец аквариумов

Ограничение по времени на тест: 1 секунды

Ограничение по памяти на тест: 256 мегабайт

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

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

Первая строка входного файла содержит натуральное число $n$ $(1 ⩽ n ⩽ 13)$ — количество городов. Следующие $n$ строк содержат по $n$ чисел — длины путей между городами.

В $i$-й строке $j$-е число — $a_{i,j}$ — это расстояние между городами $i$ и $j$ $(0 ⩽ a_{i,j} ⩽ 10^6; a_{i,j} = a_{j,i}; a_{i,i} = 0)$.

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

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

Пример

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

5
0 183 163 173 181
183 0 165 172 171
163 165 0 189 302
173 172 189 0 167
181 171 302 167 0

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

666
4 5 2 3 1

Решение

I. Замощение доминошками

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 256 мегабайт

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

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

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

Первая строка содержит числа $n$ и $m$ $(1 ⩽ n,m ⩽ 12)$. Следующие $n$ строк содержат по $m$ символов — описание доски.

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

Выведите число замощений доминошками.

Пример

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

2 2
..
..

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

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

3 3
...
.X.
...

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

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

3 3
...
...
..X

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

Решение

J. Симпатичные узоры

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер $1 × 1$ метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника $n × m$ метров.

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

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата $2 × 2$ метра, полностью покрытого плитками одного цвета.

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

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

На первой строке входного файла находятся два натуральных числа $n$ и $m$. $1 ⩽ n \cdot m ⩽ 30$.

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

Выведите в выходной файл единственное число — количество различных симпатичных узоров, которые можно выложить во дворе размера $n × m$. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением считаются различными.

Пример

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

1 1

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

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

1 2

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

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

Алгоритмы и Структуры данных

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