Задачи командного тура

A. Хлопушки

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 

1 апреля - день шуток и веселья. В этот день Вася решил пошутить над своим другом Женей. В некоторых клетках на поле размером n на m Вася поставил хлопушки.

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

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

Первая строка содержит два числа: n и m (1 <= n, m <=100). Последующие n строк описывают игровое поле - каждая из них содержит m символов. Символом "." (точка) обозначена свободная клетка, символом "*" (звездочка) - занятая хлопушкой.

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

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

Пример входного и выходного файлов

4 4 **** **.. *... *...	4
4 3 *** ... ... ***	0

B. Конфеты

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 

В день смеха Женя решил пойти в гости к Васе. Но в праздник и с пустыми руками - неприлично. Женя знает, что Вася - большая сладкоежка. И Женя пошел в магазин за конфетами. Зайдя в магазин, он увидел круглый стол с коробками конфет, причем коробки выложены только по окружности. Таким образом, у каждой коробки есть ровно две соседних. Всего на столе лежит n коробок. В каждой коробке разное количество конфет - в i-ой коробке a_i конфет. Женя решил побаловать Васю и взять три соседних коробки. Уж баловать, так баловать! Женя хочет взять коробки так, чтобы в них было максимальное количество конфет.

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

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

В первой строке содержится целое число n (3 <= n <= 1000) коробок конфет. Вторая строка содержит n целых положительных чисел a₁, a₂, ..., a_n - число конфет, находящееся в соответствующей коробке. Все a_i не превосходят 1000.

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

Единственное число - максимальное число конфет.

Пример входного и выходного файлов

4 1 2 3 4	9
3 1 2 3	6

C. СМС

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 

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

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

В первой строке записано сообщение. Оно состоит из строчных букв латинского алвафита, не пусто, и его длина не превышает 100000 символов.

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

Выведите наибольшую по длине подстроку. Если решений несколько, выведите самое левое. Если все подстроки являются палиндромами, выведите NO SOLUTION.

Пример входного и выходного файлов

abba

abb

D. Задача

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 

1 апреля Вася и Женя хотят весело провести время в цирке. Накануне преподаватель дал задание, за выполнение которого исполнители получат билет в цирк. Задание заключалось в следующем: необходимо было из n чисел 1..n, каждое из указанных чисел входит ровно один раз, найти количество способов разместить эти числа в последовательность так, чтобы любые два соседних элемента отличались не более, чем на k.

Помогите Васе и Жене попасть в цирк.

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

Первая строка содержит два целых числа n, k (1 <= k <= n <= 9).

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

Единственное число - количество способов разместить числа.

Пример входного и выходного файлов

3 1	2
4 2	12

E. Шарики

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 

Вася по дороге в цирк увидел ларек с шариками. Подойдя к нему, он узнал, что проводится первоапрельская акция: выдается столько шариков, какое число из n цифр можно получить, имея k полосок.

Любая цифра содержит семь полосок, каждая из которых может быть либо белой, либо черной. В частности, при отображении цифры "1" черными являются две полоски.

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

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

Первая строка содержит два целых числа (1 <= n <= 100, 1 <= k <= 700).

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

В первой строке выведите минимальное число шариков, во второй строке максимальное число. Если указанным образом не может быть представлено не одно число, выведите единственную строку NO SOLUTION.

Пример входного и выходного файлов

5 15	10117 97111
10 1	NO SOLUTION