Задача A. Сколько программ? ≡

Условие

Женя любит программировать! Она уже выучила N конструкций! Жене интересно, сколько программ заданной длины L она может составить из этих конструкций. Помогите ей сосчитать программы!

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

Женя не требует, чтобы полученная программа компилировалась. Про компиляторы она еще не прочитала.

Формат входного файла

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

Все строки содержат только символы с ASCII-кодами от 32 до 126. Кроме того, Женя хочет, чтобы пробелы в строках игнорировались (все остальные символы учитываются при подсчете длины).

В последней строке входного файла содержится число L.

Формат выходного файла

Ограничения

Примеры тестов

3
begin
clrscr
end
17

20

Задача B. Небольшая подтасовка ≡

Условие

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

По новому плану столица будет разделена прямоугольной сеткой, в качестве сторон которой будут выбраны главные улицы и авеню. Все улицы и авеню проходят через весь город, имеющий форму прямоугольника, параллельно его сторонам (улицы — вертикально, а авеню — горизонтально). Нумерация начинается с левого нижнего угла. Город ограничивают четыре дороги: 1-я улица (левая граница), 100-я улица (правая граница), 1-я авеню (нижняя граница), 100-я авеню (верхняя граница). Очевидно, что эти дороги должны ограничивать округа, однако, не все дороги по плану будут являться границами округов. Кроме того, для соблюдения видимости честности Либеративы будут определять только вертикальные границы округов, в этом и заключается Ваш шанс, т.к. они вынуждены позволить Консервалам определять горизонтальные.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2
49 49 
50 50
2 1 100
3

3 1 50 100

Задача C. Лабиринт знаний ≡

Условие

Участникам сборов подарили билеты на аттракцион ``Лабиринт знаний''. Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате N. Каждый участник сборов проходит лабиринт ровно один раз и наибрает некоторое количество знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача — показать наилучший результат.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 2
1 2 5
1 2 -5

5

Задача D. Заправки ≡

Условие

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

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4
1 10 2 15
4
1 2 1 3 4 2 4 3

2

4
1 10 2 15
0

-1

Задача E. Форматирование таблицы ≡

Условие

Вам предлагается отформатировать таблицу, данную во входном файле.

Формат входного файла

Формат выходного файла

1. самая длинная запись должна быть отделена от правого и левого краев ячейки ровно одним пробелом.
2. если запись не может быть расположена точно посередине, то все дополнительные пробелы появляются справа от нее.

Ограничения

1. длина любой строки входного файла не превышает 250 символов
2. в таблице не более 100 строк
3. в таблице не более 100 столбцов

Примеры тестов

lr
EXPRESSION&RESULT
2+2&4
2+2*2&6

+------------+--------+
| EXPRESSION | RESULT |
+------------+--------+
| 2+2        |      4 |
| 2+2*2      |      6 |
+------------+--------+

lcr
LEFT&CENTER&RIGHT
1&2&3
the&the&the
longest&longest&longest
kitten&kitten&kitten
blitz&blitz&blitz

+---------+---------+---------+
| LEFT    | CENTER  |   RIGHT |
+---------+---------+---------+
| 1       |    2    |       3 |
| the     |   the   |     the |
| longest | longest | longest |
| kitten  | kitten  |  kitten |
| blitz   |  blitz  |   blitz |
+---------+---------+---------+