microbik.ru
1 2 ... 10 11

Задача A. Домой на электричках


Имя входного файла:

a.in

Имя выходного файла:

a.out

Максимальное время работы на каждом тесте:

2 секунды

Максимальный доступный объем памяти:

8 мегабайт

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

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

Формат входных данных


Во входном файле записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ EN). Затем записано число M (2 ≤ M ≤ 50), обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki (2 ≤ KiN) - количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе - время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении - либо от города, либо к городу.

Формат выходных данных


В выходной файл выведите одно число - минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите -1.

Пример


a.in

a.out

5 3

4

2 1 5 2 10

2 2 10 4 15

4 5 0 4 17 3 20 2 35

3 1 2 3 40 4 45

20

Задача B. Рамка


Имя входного файла:

b.in

Имя выходного файла:

b.out

Максимальное время работы на каждом тесте:

2 секунды

Максимальный доступный объем памяти:

8 мегабайт

Рассмотрим прямоугольник размером X × Y, из середины которого вырезали прямоугольник размером (X - 2) × (Y - 2). Назовем такую геометрическую фигуру рамкой размера X × Y. На рисунке 1 изображена рамка размера 5 × 6.



Предположим, что у нас имеется неограниченный запас плиток размера ^ A × 1. Рассмотрим следующую задачу: можно ли полностью замостить рамку размера X × Y такими плитками (плитки разрешается поворачивать на 90 градусов). Например, рамку 5 × 6 можно полностью замостить плитками размера 3 × 1 (например, как это сделано на рисунке 2), а плитками размера 4 × 1 - нельзя.

Формат входных данных


Первая строка входного файла содержит два целых числа - X и Y (3 ≤ X, Y, ≤ 106). Вторая строка содержит число N - количество видов плиток, которые следует проанализировать (1 ≤ N ≤ 1000). Третья строка содержит N натуральных чисел, не превышающих 106. Обозначим i-ое число третьей строки входного файла за Ai.

Формат выходных данных


Выведите в выходной файл N строк, i-ая строка должна содержать слово yes, если можно замостить рамку размера X × Y плитками размера Ai × 1 и no в противном случае.

Пример


b.in

b.out

5 6

2

3 4

yes

no

Задача C. Умный чертежник


Имя входного файла:

c.in

Имя выходного файла:

c.out

Максимальное время работы на каждом тесте:

2 секунды

Максимальный доступный объем памяти:

8 мегабайт

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

Этот робот умеет выполнять программу, которая может состоять из команд E, W, N, S - переместиться по листу в соседнюю вершину сетки вправо, влево, вперед, назад соответственно. Перемещаясь в соседний узел сетки, робот оставляет за собой ровную линию. При этом по правилам техники безопасности ему категорически запрещается проводить дважды одну и ту же линию, так как при попытке провести линию второй раз, он очень сильно пачкается в своих же собственных чернилах (они очень долго сохнут), и выходит из строя.

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



В первом случае мы оба раза проезжаем через вершину "прямо" (будем называть это самопересечением маршрута), а во втором случае - оба раза "поворачиваем" (это будем называть самокасанием).

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

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

Формат входных данных


В первой строке входного файла содержится программа для робота. Таким образом, в первой строке входного файла могут встречаться только символы E, W, N, S, а также пробельные символы, которые должны игнорироваться. Общая длина строки (включая пробельные символы) не превышает 200 символов.

Формат выходных данных


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

Пример


c.in

c.out

EENWSSWNN

ENESWSWNN


следующая страница >>