суббота, 30 марта 2013 г.

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



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-ой коробке ai конфет. Женя решил побаловать Васю и взять три соседних коробки. Уж баловать, так баловать! Женя хочет взять коробки так, чтобы в них было максимальное количество конфет.
Напишите программу для нахождения максимального числа конфет, которое возьмет Женя.
Формат входного файла
В первой строке содержится целое число n (3 <= n <= 1000) коробок конфет. Вторая строка содержит n целых положительных чисел a1, a2, ..., an - число конфет, находящееся в соответствующей коробке. Все ai не превосходят 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" черными являются две полоски.

цифры 0 1 2 3 4 5 6 7 8 9

Напишите программу, которая выведет минимальное и максимальное число из n цифр, используя ровно k черных полосок. Учитывайте при этом, что числа не могут содержать ведущие нули.
Формат входного файла
Первая строка содержит два целых числа (1 <= n <= 100, 1 <= k <= 700).
Формат выходного файла
В первой строке выведите минимальное число шариков, во второй строке максимальное число. Если указанным образом не может быть представлено не одно число, выведите единственную строку NO SOLUTION.
Пример входного и выходного файлов
5 15
10117
97111
10 1
NO SOLUTION

Комментариев нет:

Отправить комментарий