За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.
Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трех билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).
На вход программы поступает сначала число N — количество покупателей в очереди (1≤N≤5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.
Требуется вывести одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.
5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1
12
| 7 | 8 | 9 |
| 4 | 5 | 6 |
| 1 | 2 | 3 |
| 0 |
Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.
Вводится одно целое число N (1 ≤ N ≤ 20).
Выведите искомое количество телефонных номеров.
1
8
10
11728
Квадратный клетчатый лист бумаги 2N × 2N клеток начинают складывать следующим образом. Сначала нижняя половина листа накладывается на верхнюю, затем правая половина листа накладывается на левую. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8 × 8 клеток. Какие-то из клеток этого сложенного листа удаляются при помощи дырокола.
После развертывания исходный лист распадется на некоторое количество связных частей, т.е. таких множеств клеток, что из любой клетки одного множества можно пройти до любой другой, переходя каждый раз на соседнюю по вертикали или горизонтали клетку. Напишите программу, вычисляющую число частей, на которые распадется лист.
Первая строка входных данных содержит целое число N (4 ≤ N ≤ 500). В следующих 8 строках задается матрица 8 × 8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8 × 8.
Требуется вывести искомое число частей.
Заданы последовательности, которые могут быть заменены некоторыми символами английского алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти последовательности могут накладываться друг на друга, результат сжатия существенно зависит от порядка замен. Ваша задача состоит в том, чтобы получить сжатый текст наименьшей длины.
Входные данные
В первой строке входных данных заданы целое число 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ый текст наименьшей длины.
Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение «No solution!»
AB? *BC
ABC