#213

Ход конем

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

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

7	8	9
4	5	6
1	2	3
	0

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

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

Вводится одно целое число N (1 ≤ N ≤ 20).

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

Выведите искомое количество телефонных номеров.

Примеры

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

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

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

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

#214

Дырокол

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

Квадратный клетчатый лист бумаги 2^N × 2^N клеток начинают складывать следующим образом. Сначала нижняя половина листа накладывается на верхнюю, затем правая половина листа накладывается на левую. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8 × 8 клеток. Какие-то из клеток этого сложенного листа удаляются при помощи дырокола.

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

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

Первая строка входных данных содержит целое число N (4 ≤ N ≤ 500). В следующих 8 строках задается матрица 8 × 8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8 × 8.

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

Требуется вывести искомое число частей.

#215

Сжатие текста

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

решать

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

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

Входные данные
В первой строке входных данных заданы целое число R (1 ≤ R ≤ 52) – количество заменяемых последовательностей и целое число N – количество строк в исходном тексте (1 ≤ N ≤ 1000). Далее следуют R пар строк, описывающих возможные замены. Первая строка каждой пары содержит заменяемую последовательность, а вторая – заменяющий символ, являющийся большой или маленькой английской буквой. Различным заменяемым последовательностям соответствуют разные английские буквы (большие и маленькие буквы различаются). В следующих N строках записан текст, подлежащий сжатию. В этом тексте так же, как и в заменяемых последовательностях, отсутствуют буквы английского алфавита.

Выходные данные
Требуется вывести заархивированный текст.

Примечания
Символы перевода строки не заменяются (т.е. замены возможны только внутри строк). Длина каждой строки входного файла не превосходит 255 символов.

Пример

Входные данные
8 10
рхиватор
b
замен
D
ены
F
зам
G
быт
h
про
d
сжат
f
ом называется
g
Архиватором называется программа, предназначенная для сжатия данных за счет удаления
избыточной информации. В этой задаче вашей целью является разработка простейшего
архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы
символов не встречаются, поэтому они могут быть использованы для замены часто
повторяющихся последовательностей символов.

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

Выходные данные
Аbg dграмма, предназначенная для fия данных за счет удаления
изhочной информации. В этой задаче вашей целью является разработка dстейшего
аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы
символов не встречаются, поэтому они могут hь использованы для Dы часто
повторяющихся последовательностей символов.

Заданы последовательности, которые могут hь DF некоторыми символами английского
алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти
последовательности могут накладываться друг на друга, результат fия существенно зависит
от порядка D. Ваша задача состоит в том, чтобы получить fый текст наименьшей длины.

#217

Шаблон с ? и *

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

Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.

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

Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

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

Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение «No solution!»

Примеры

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

AB?
*BC

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

ABC

#218

Жадный калькулятор

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

Задано алгебраическое выражение, составленное из неотрицательных вещественных чисел и знаков операций +, - и *. Требуется так расставить в этом выражении скобки, чтобы его значение стало максимально возможным.

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

Исходное выражение длиной не более 250 символов записано в первой строке входных данных. Выражение содержит не более 50 чисел, каждое из которых лежит в диапазоне от 0 до 10⁶ . Пробелы внутри чисел не допускаются.

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

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

Примеры

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

3                 +            5     *   150

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

1200
((3+5)*150)

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

2+3*0.02*4*0.02*5

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

10.024
((2+(3*(0.02*(4*0.02))))*5)