Задача A. Индикатор загрузки

Входной файл:pbar.in   Ограничение времени на тест:2 сек
Выходной файл:pbar.out   Ограничение памяти на тест:64 Mebibytes

Условие

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

Индикатор загрузки представляет собой поле n × m пикселей, отражающее состояние загрузки некоторого файла размером n  m байт. Все пиксели индикатора нумеруются от 1 до n  m слева направо сверху вниз, при этом пиксель c номером i окрашен в чёрный цвет, если i-й по счёту байт файла уже загружен, и в белый цвет — в противном случае.

Для ускорения загрузки файл был разделён на равные фрагменты по b байт, каждый из которых загружается одновременно. Байты внутри одного фрагмента загружаются последовательно от начала к концу.

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

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

В первой строке входного файла находятся целые числа n m b. Вторая строка содержит четыре числа r1 c1 r2 c2 — координаты видимой части индикатора. Следующие r2 − r1 + 1 строк по c2 − c1 + 1 символов каждая описывают видимую часть изображения: строки с r1-й по r2-ю, столбцы с c1-го по c2-й. Символ '=' (ASCII 61) обозначает чёрный пиксель, символ '.' (ASCII 46) — белый.

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

Выходной файл должен содержать два целых числа — минимально и максимально возможное число байт, загруженных к данному моменту.

Ограничения

1  n, m  104, 1  b  n  m, n  m делится на b нацело.

1  r1  r2  n, 1  c1  c2  m, r2 − r1  100, c2 − c1  100.

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

Входной файлВыходной файл
1
5 7 5
2 3 2 3
.
0 28
2
5 7 5
1 5 3 7
.==
==.
..=
21 21

Задача B. Нарезка фантиков

Входной файл:cut.in   Ограничение времени на тест:2 сек
Выходной файл:cut.out   Ограничение памяти на тест:64 Mebibytes

Условие

Для производства конфетных фантиков изготовлена длинная узкая лента с напечатанными на ней картинками. Длина каждой картинки — L мм, расстояние между двумя соседними картинками — d мм, расстояние от начала ленты до первой картинки — a мм.

Нужно получить N фантиков длиной W мм каждый. Аппарат по производству фантиков работает так: сперва от начала ленты отрезается и выбрасывается кусок длиной x мм. Затем от начала ленты один за другим отрезаются фантики длиной W мм каждый.

Каким должно быть x, чтобы на каждом фантике была целиком расположена ровно одна картинка? Картинки, попадающие на фантик только частично, не считаются.

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

Входной файл содержит целые числа L d a N W.

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

Выходной файл должен содержать целое число x.

Число x должно удовлетворять неравенству 0  x < L + d.

Если существует несколько решений, выведите любое из них.

Ограничения

1  N, L, W, d  1000.

0  a < L+d.

Гарантируется, что существует хотя бы одно решение.

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

Входной файлВыходной файл
1
3 1 2 3 7
1



Задача C

Грибной дождь


Input file: growling.in

Output file: growling.out

Time limit: 2 seconds

Memory limit: 64 Mebibytes


На лесной опушке растет дружная семейка грибов. Местоположение каждого гриба задается координатами X, Y, а шляпка гриба имеет радиус R. Когда идет дождь, радиус шляпки каждого гриба увеличивается cо скоростью 1 сантиметр в минуту. Когда дождь заканчивается(а он идет не более Т минут), шляпки прекращают расти. Если во время дождя шляпки двух грибов соприкоснулись, то они немедленно перестают расти, чтобы не навредить друг другу. Грибы очень дружные, поэтому если перестают расти два гриба, то и все остальные тоже не растут.

Ваша задача: посчитать, на сколько сантиметров увеличился радиус шляпки каждого гриба после завершения дождя.

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

Первая строка содержит число N – количество тестов. Первая строка теста содержит два целых числа: количество грибов K (K<=10) и длительность дождя T (T<=100). Следующие К строк содержат описание грибов: координаты X и Y (X<=100,Y<=100) и радиус шляпки R (R<=10). Координаты и радиус даны в сантиметрах.

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

Для каждого теста вывести одно число – величину, на которую увеличится радиус всех грибов. Результат не должен содержать незначащих нулей и должен быть выведен с точностью до двух знаков после запятой.


Пример входных данных

Пример выходных данных

2

2 1

0 0 1

2 2 1

3 2

0 0 1

5 5 1

10 10 1

0.41

2.00



Задача D

Сон

Input file: dream.in

Output file: dream.out

Time limit: 2 seconds

Memory limit: 64 Mebibytes


Любознательный школьник Петя очень любит программировать. Однажды он настолько увлекся этим делом, что уснул прямо за компьютером! Пете приснилось, что он попал в альтернативную реальность. Альтернативная реальность представляет собой прямоугольный лабиринт, который можно изобразить в виде таблицы размером R × C клеток. Чтобы не опоздать в школу, Пете нужно найти выход из лабиринта. Начальная позиция Пети обозначается символом ‘S’, выход из альтернативной реальности – ‘E’. За один ход Петя перемещается в одну из четырех смежных клеток (влево, вправо, вниз, вверх). Если клетка занята стеной (символ ‘X’), то Петя пройти в нее не может. В некоторых клетках расположены двери с замками одного из четырех цветов (‘R’, ‘G’, ‘B’, ‘Y’). Для прохода в эту клетку, необходимо обладать ключом определенного цвета. Так как ключи многоразовые, то одним ключом можно открыть сколь угодно много соответствующих ему замков.

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

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

Первая строка входного файла содержит число тестов. Каждый тест начинается с двух целых чисел R и C (1 <= R, C <= 50). Вторая строка теста содержит 4 целых числа Pi, стоимости покупки ключей ‘R’, ‘G’, ‘B’ и ‘Y’ соответственно (Pi <= 100). Далее следуют R строк, в каждой из которых C символов, описывающих лабиринт. Каждый лабиринт содержит только один символ ‘S’ и один символ ‘E’.

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

Для каждого теста на отдельной строке выведите минимальную сумму денег, необходимую для покупки набора ключей, позволяющего пройти к выходу. Если пути к выходу из альтернативной реальности не существует, и Петя обречен проспать уроки, выведите «Sleep».


Пример входных данных

Пример выходных данных

2

3 7

1 1 1 1

XXXXXXX

XS.X.EX

XXXXXXX

6 6

1 5 3 1

XXXXXX

XS.X.X

X..R.X

X.XXBX

X.G.EX

XXXXXX

Sleep

4




Задача E

Лентяй

Input file: bad.in

Output file: bad.out

Time limit: 2 seconds

Memory limit: 64 Mebibytes


Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

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

Первая строка входных данных содержит количество тестов. Каждый тест состоит из числа N – количество предметов, которые нужно сдать Валере
(1<= N <=100). Далее идет N строк, каждая из которых состоит из двух чисел A и B, задающих интервал работы очередного преподавателя (1 <= A <= B <= 31).

Пример входных данных

2

1

1 2

2

1 2

3 4

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

Для каждого теста программа должна вывести в выходной файл в отдельной строке “YES” если возможно встретить всех преподавателей за один день, или “NO”, если это невозможно.

Пример выходных данных

YES

NO

Задача F. Настройка гитары

Входной файл:guitar.in   Ограничение времени на тест:2 сек
Выходной файл:guitar.out   Ограничение памяти на тест:64 Mebibytes

Условие

Однажды программист Вася решил научиться играть на гитаре. Первым делом он выучил правила настройки гитары.

Первая струна настраивается по камертону. Каждая следующая струна настраивается по предыдущей, а именно:

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

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

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

i-ый символ входной строки показывает как звучит (i+1)-ая струна относительно i-ой, а именно:

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

В выходном файле должна содержаться строка из 5 символов, описывающая действия, которые требуется произвести для настройки гитары. В i-ой позиции строке должен содержаться символ, описывающий действие над (i+1)-ой струной:

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

Входной файлВыходной файл
1
=====
*****
2
=<=<=
*++++
3
>==<=
---??