Олимпиада по программированию
"Университеты Алтая - 2007"

      
A. Светофоры
B. Макросы
C. К чему приводит защита от копирования
D. Названия стихотворений
E. Поход за грибами
F. Забор Копатыча
G. Выведи хомячков
H. Хомячки на торе
I. Компотозаготовка
J. Поиски сокровищ
K. Большой секрет
L. Шаманский бубен
M. Центральное отопление
      

Задача A. Светофоры

Имя входного файла: lights.in
Имя выходного файла: lights.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
Как-то раз Крош снова взял страшную челюсть и стал с ней бегать по лесу, пугая всех в округе. В этот раз все настолько испугались, что стали лихорадочно и беспорядочно бегать, сталкиваясь друг с другом и вытаптывая грядки Копатыча, предварительно снеся забор Копатыча, любовно выстроенный вокруг грядок.

И один лишь практичный Ежик не испугался, а подумал, что если такое будет продолжаться регулярно, то скоро лес превратится в степь, а затем в пустыню. Не будет ни грядок Копатыча, ни дерева Совуньи... Чтобы предотвратить хаос и вселенскую катастрофу, Ежик решил не сидеть дома сложа иголки, а действовать. По его гениальному Плану Спасения Мира (сокращенно ПСМ), необходимым и достаточным условием было установление светофоров посередине всех дорог леса, что заставило бы Кроша и пугливых лесных обитателей бегать не лихорадочно и хаотично, а в строгом соответствии с Правилами Дорожного Движения (сокращенно ПДД).

Для реализации этого хитроумного плана, Ежик попросил Пина собрать и установить светофоры на всех серединах улиц, пообещав ему за это достать лицензионный дистрибутив Microsoft Windows Vista. Услышав это, Пин жутко разозлился. В самом деле, предлагать ЕМУ, лично знающему Tux'а ТАКОЕ?! Но заняться Пину было все равно нечем, а поэтому он все же помог Ежику. Правда, чтобы в следующий раз Ежик предлагал ему нормальный софт, он установил всего лишь демо-версию светофоров «Lights 0.9.6 pre5 try7 beta3 build 4559», в которых отсутствовал желтый цвет. Также, чтобы все было не так скучно, Пин присвоил каждому светофору свой период переключения.

Увидев все это, Крош решил «объяснить» Ежику, что он был неправ, причем он захотел это сделать как можно быстрее. Предварительно для этого «объяснения» он приготовил при помощи челюсти максимально страшное выражение, которого боялся даже сам Крош, когда видел его в зеркале. Чтобы добраться до Ежика, Крош подобрал момент, когда все светофоры одновременно включились и уже решил побежать, но тут понял, что бежать-то можно разными путями, а хочется добежать как можно быстрее. По этой причине он попросил вас написать программку, которая определит минимальное время, за которое он сможет добраться до Ежика. Сам путь Крошу не нужен – зная лес, он легко определит, куда бежать, если знает время. В начальный момент времени Крош находится на перекрестке с номером 1. Домик Ежика расположен около перекрестка с номером N.

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

В первой строке через пробел записаны целые числа N, M и действительное число V, где N – количество перекрестков, M - количество дорог, V – скорость движения Кроша ( N ≤ 100, M < 10000, 0 < V ≤100). В каждой из последующих строк находятся описания дорог в виде четырех чисел – A, B, L, P, где A - начальный, B - конечный перекрестки (A, B ≤ N), L - длина дороги, P – период переключения светофора в середине данной дороги (L,P ≤ 100). Учтите, что числа L и P могут быть дробными. Два перекрёстка может соединять только одна дорога.

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

Вывести единственное вещественное число с двумя знаками после запятой – минимальное время в секундах, за которое Крош сможет добраться до Ежика.

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

lights.in                 lights.out                
3 2 5
1 2 5 1
2 3 5 1
2.50
      

Задача B. Макросы

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

Однажды Бараш решил поучаствовать в литературном конкурсе программистов. Стихотворения принимались на четырех языках: Assembly, Foxy, Lispy, Prology. Как старый поэт-программист, Бараш признавал только Assembly. Поэтому писать пришлось на нем. Он запустил свой верный edit.com под Dos 6.22 и приступил к делу. Учитывая то, что Бараш был ленивым программистом, он вовсю использовал макросы. Это чрезвычайно ускоряло процесс стихосложения, так как у Бараша было множество заготовок, как и у любого старого поэта-программиста.

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

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

 

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

 

Дано стихотворение, содержащее макроопределения. Формат макроопределений имеет следующий вид (вместо каждого символа ‘_’ во входном и выходном файлах будет стоять точно один пробел):

1. Макроопределения:

#identificator_{<text>}

Идентификатор (имя макроопределения) состоит не более, чем из 10 строчных латинских букв. Не встречается макроопределений с именем “rep”.

2. Макровызовы:

##identificator_

3. Циклические макроопределения:

#rep_n_{<text>}

n – целое число повторов текста <text> (0 <= n <= 100).

Назовем блоком текст <text>, заключенный между фигурными скобками. Bсе стихотворение также называется блоком. В любом блоке могут встречаться другие макроопределения и макровызовы.

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

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

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

Исправленный текст стихотворения.

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

macros.in                 macros.out                
##a_
#a_{a}##a_
#b_{##a__#a_{b}##a_#c_{##a_}_##c_}
##b_##c_
##a_

a

a_b_b
a
      

Задача C. К чему приводит защита от копирования

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

 

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.

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

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

На первой строке два числа N (N ≤ 100) и M - количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих M строках перечисляются пары чисел U и V, означающих, что смешарик U и смешарик V знакомы друг с другом и обмениваются мультфильмами.

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

Вывести минимальное число у.е., которое придется затратить Билашу на достижение своей цели.

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

bilash.in                 bilash.out                
5 5
1 2
2 3
3 5
5 2
2 4
1
      

Задача D. Названия стихотворений

Имя входного файла: forbidden.in
Имя выходного файла: forbidden.out
Ограничение по времени: 3 секунды
Ограничение по памяти: 64 Mb

 

На недавно прошедшем референдуме смешарики приняли поправки к статье «Названия стихотворений» закона «О Защите Авторских Прав». Раньше закон требовал, чтобы называния стихотворений были последовательностями из 0 и 1. А сейчас необходимо, чтобы название каждого нового стихотворения не только состояло из 0 и 1, но и не содержало в себе названий других, уже опубликованных произведений.

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

Узнав о таких изменениях в законодательстве, Бараш решил называть все свои шедевры последовательностями длины К.  Он зашел на сайт смешариков и увидел, что в списке уже есть N чужих произведений. Ему стало интересно, сколько еще стихотворений он сможет сочинить, не нарушая новый закон. Начав считать, Бараш понял, что это слишком сложно и ему с этим не справиться. Помогите Барашу определить, сколько стихотворений он сможет сочинить. Бараш подозревает, что таких стихотворений будет слишком много, поэтому он просит вывести не все число, а взятое по модулю P.

 

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

В первой строке даны три числа N, К ( K ≤ 1000) и P (P ≤ 2*109). В последующих N строках записан список названий. Каждое название представляет собой последовательность нулей и единиц. Длина слов не превышает 15. Известо, что до принятия закона некоторые названия стихотворений могли совпадать, но из списка их не изъяли.

 

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

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

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

forbidden.in                 forbidden.out                
2 3 100
10
01
2
      

Задача E. Поход за грибами

Имя входного файла: mushrooms.in
Имя выходного файла: mushrooms.out
Ограничение по времени: 3 секунды
Ограничение по памяти: 64 Mb
Однажды летним утром Копатыч отправился в гости к Ёжику. Копатыч подумал, что идти в гости с пустыми руками невежливо, и решил по дороге набрать для своего друга больших вкусных грибов. Для этого он взял бо-о-ольшую корзинку и потопал в лес. Мишка хочет, чтобы каждый следующий гриб был больше по весу, чем предыдущий, ведь так гораздо интереснее. Лес представляет собой прямоугольник размера N*M прыжков Кроша (пК). На каждом квадратном пК растёт ровно один гриб. Копатыч хочет собрать как можно больше грибов, при этом не возвращаясь назад (ведь он идёт к Ёжику!), то есть каждый следующий сорванный Копатычем гриб должен находиться южнее и восточнее предыдущего. Копатыч может начать и прекратить сбор грибов, находясь в любом месте леса, после чего он направляется к Ёжику. Какое максимальное количество грибов получит Ёжик в подарок.

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

На первой строке два натуральных числа N и M (N,M ≤ 500) – длина и ширина леса в прыжках Кроша (пК). На каждой из последующих N строк записано по M чисел – вес гриба в граммах на соответствующей поляне. Вес каждого гриба не превышает 1000 граммов.

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

Выходной файл должен содержать одно число - максимальное количество грибов, которые получит Ежик от Копатыча.

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

mushrooms.in                 mushrooms.out                
3 4
1 6 8 2
3 4 5 3
1 1 3 2
2
5 5
5 1 10 13 4
80 3 8 9 6
1 4 7 8 10
17 2 9 90 3
18 5 16 7 30
3
      

Задача F. Забор Копатыча

Имя входного файла: fence.in
Имя выходного файла: fence.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
Чтобы оградить свои грядки от непрошенных посетителей (особенно после безобразия с челюстью Кроша) задумал Копатыч построить забор. Друзья решили сделать ему подарок ко дню рождения и помочь в этом нелегком деле. Чтобы сделать приятное другу, все решили принять участие в постройке забора. А чтобы построенный забор оказался сюрпризом, смешарики вышли на дело ночью. Каждый построил какой-то кусочек забора. К сожалению, в темноте плохо видно, поэтому отдельные заборчики оказались разбросаны по огороду. Пришло утро, Смешарики увидели творение своих рук и решили убрать лишние заборчики так, чтобы остался один самый длинный прямой забор.

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

На первой строке дано число N (N≤ 10000) – количество смешариков, которые принимали участие в строителеьстве забора. На каждой i-ой из последующих N строк записаны по четыре целых числа x1, y1, x2, y2– координаты начальной и конечной точек забора, который построил i-ый смешарик. Координаты не превышают по абсолютной величине 1000.

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

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

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

fence.in                 fence.out                
3
1 1 1 2
1 2 1 3
-1 -1 -1 -2
2.00
      

Задача G. Выведи хомячков

Имя входного файла: hamsters.in
Имя выходного файла: hamsters.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
Однажды в домик Лосяша постучалось несколько хомячков. Все они тихонько хлюпали носиками и вытирали заплпканные глазки. "Что случилось?" - спросил Лосяш, и услышал в ответ ужасное сообщение: два хомячка заблудились в вентляционной системе, которую соорудил Пин для охлаждения своего суперкрутого компа. Лосяш решил помочь хомячкам спасти своих товарищей. Проблема в том, что единственный способ помочь зверькам - это передать им по радио команды. Помогите Лосяшу написать программу спасения хомячков.
Лабиринт вентиляции представляет собой плоскую прямоугольную пластину с прорезанными внутри полостями. В лабиринте имеется ровно один выход. Хомячки не отличаются умом и сообразительностью и сами выбраться из лабиринта не могут. Зато они могут выполнять набор команд. Команды подаются обоим хомячкам одновременно. Хомячки двигаются с одинаковой скоростью. Команды бывают следующих типов:

Для простоты будем считать, что лабиринт состоит из клеток. Каждая клетка может быть либо проходом, либо стеной, либо выходом. Хомячки могут одновременно находиться на одной клетке. Через стену вентиляции хомячки ходить не могут. Более того, они так отупели от блуждания в лабиринте, что могут выйти из лабиринта только вдвоём. Если по клетке-выходу проходит только один хомячок, то он не выходит из лабиринта и продолжает выполнять команды.

Входные данные (файл hamsters.in)

В первой строке заданы два целых числа H и W - размеры лабиринта по вертикали и горизонтали соответственно. Далее следует H строк по W символов, каждый из которых может быть: * - выход, 1 - первый хомячок, находящийся в проходе, 2 - второй хомячок, находящийся в проходе, . - свободная дорожка, # - пропасть. H, W<= 100.

Выходные данные (файл hamsters.out)

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

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

hamsters.in                 hamsters.out                
4 5
.....
.....
...2.
..1*.
4
RRLD
      

Задача H. Хомячки на торе

Имя входного файла: tor.in
Имя выходного файла: tor.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
После спасения двух своих друзей из вентиляции хомячки устроили весёлый праздник. Они пригласили всех смешариков, стали пить чай и грызть всё подряд. А потом хомячки притащили огромную баранку и предложили смешарикам сыграть с ними в игру. Смешарики по очереди говорят хомячкам команды, а хомячки бегают по баранке, выполняя их.

Баранка представляет собой клетчатый тор размером W*H. Всего в празднике участвует N хомячков. Все хомячки разные, для простоты пронумеруем их от 0 до N-1. После спасения из системы вентиляции хомячки резко поумнели, и теперь могут выполнять набор очень сложных команд. Очередная команда подается хомячку с номером, равным сумме координат всех хомячков по модулю N. Команды бывают следующих типов:

Определите, где будут находиться все хомячки после игры.

Входные данные (файл tor.in)

В первой строке заданы три целых числа W, H - размеры тора по горизонтали и вертикали соответственно (H, W ≤ 100000), и N - число хомячков (N ≤ 1000). Во второй строке находится N пар чисел - исходные координаты хомячков. Хомячки нумеруются, начиная с нуля. Координаты ограничены размерами баранки: 0 ≤ X < W, 0 ≤ Y < H. В предпоследней строке задано M - количество команд, 0 ≤ M ≤ 1000 В последней строке находится программа. Команды перечисляются через пробел.

Выходные данные (файл tor.out)

Для каждого i-ого хомячка в i-ой строке вывести его координаты после исполнения команд.

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

tor.in                 tor.out                
3 3 2
1 1
2 2
3
R U L
2 1
1 0
      

Задача I. Компотозаготовка

Имя входного файла: compot.in
Имя выходного файла: compot.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
Ежегодно Совунья заготавливает на зиму компоты для себя и своих друзей. Фрукты, которые она использует для этого, растут на том же дереве, где находится ее домик. Все было бы хорошо, если бы ее дерево не росло, а вместе с ним не увеличивались бы урожаи фруктов. В один прекрасный вечер, заготавливая компоты,  она поняла, что просто не справляется с возросшим количеством фруктов.

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

В итоге деятельности Пина агрегатов стало на K больше, чем было до этого, и общая производительность комплекса увеличилась. Все агрегаты имеют одинаковую производительность, выражаемую в банках в час.  Если до реконструкции производство Совуньи в целом выдавало N банок компота в день, то после реконструкции оно стало выдавать в целом M банок компота в день. Впрочем, это не стало означать, что стал оставаться лишний компот – просто его стали быстрее выпивать.

Напишите программу, которая по входным данным, числам K, N, M определит, сколько компотных агрегатов могло быть до реконструкции, и выведет все возможные варианты ответов в порядке возрастания в выходной файл. Считается, что возможные варианты есть всегда.

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

Последовательно в строках входного файла записаны целые числа K, N, M (0 < K, N, M ≤ 2000000000).

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

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

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

compot.in                 compot.out                
3
16
35
2
4
      

Задача J. Поиски сокровищ

Имя входного файла: password.in
Имя выходного файла: password.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
Однажды Лосяш нашел древний манускрипт, содержащий карту пути к древней пещере, в которой лежали сокровища далёких предков Смешариков. Всем известно, что древние Смешарики были высокоинтеллектуальной народностью, поэтому дверь в пещеру была защищена паролем. В древнем манускрипте содержалась информация о том, как подобрать пароль. У древних Смешариков было магическое заклинание, которое они использовали для вызова злых духов. На двери в пещеру была выбита куча точечек, которые были соединены стрелочками. Над каждой стрелочкой была написана строчная буковка латинского алфавита. Древнее пророчество гласило, что пароль можно получить, пройдя по стрелочкам от некоторой конкретной точечки (волшебной) до какой-то другой. Более того, Лосяш выяснил, что пароль содержится в магическом заклинании для вызова злых духов как подстрока ровно k раз. Помогите Лосяшу найти пароль и открыть миру сокровища древней народности Смешариков. Если вариантов пароля, отвечающих данным условиям, несколько, то сгодится любой. Также учтите, что манускрипт Лосяшу могли подбросить враги. В этом случае пароля не существует.

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

На первой строке находится заклинание. Длина магического заклинания L≤ 105. На второй строчке находятся числа N и M (N, M ≤ 105) – число точечек и число стрелочек. В следующих M строчках содержится информация о стрелочках: номер стартовой точечки, номер конечной точечки и строчная буковка латинского алфавита. На последней строчке содержится число k (1 ≤ k≤ L). Внимательно анализируя картинку на двери в пещеру, Лосяш заметил, что количество различных путей из волшебной точечки в остальные не превышает 105. Зато Лосяш обрадовался, что все переходы детерминированы, то есть из каждой по любому символу существует не более одного пути.

Начальной волшебной точкой является точка с номером 1. Все точки нумеруются с единицы.

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

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

Если паролей не существует, то выходной файл остается пустым. Гарантируется, что длина выходного файла не превышает 120000 символов.

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

password.in                 password.out                
ssssabaabbsss
2 1
1 2 a
3
a
      

Задача K. Большой секрет

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

Однажды известный коллекционер фантиков Ёжик провёл презентацию своей коллекции. Коллекция была столь потрясающей, что все смешарики, кроме Нюши, решили заняться коллекционированием фантиков. Коллекционировать просто так неинтересно, главное в этом процессе – обмен. Сначала процедура обмена была стихийная, в результате чего между смешариками постоянно происходили ссоры. Мудрая Совунья решила упорядочить процесс обмена и составила список, кто из смешариков кому отдаёт свои фантики. Во избежание новых ссор, список был составлен таким образом, что каждый смешарик отдавал свои фантики только одному конкретному смешарику и получал фантики тоже только от одного конкретного смешарика (смешарик, которому он отдаёт фантики и смешарик, от которого он получает фантики могут совпадать).

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

 

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

На первой строке входного файла находится число тестов T(1<=T<=100). На следующих T строчках находится по одному числу – количество смешариков N, задействованных в обмене (1<=N<=100).

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

Для каждого теста выведите строчку «Case #K: R», где K – номер теста, R – ответ для данного теста.

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

secret.in                 secret.out                
3
2
3
4
Case #1: 1
Case #2: 2
Case #3: 9
      

Задача L. Шаманский бубен

Имя входного файла: buben.in
Имя выходного файла: buben.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
Как-то раз Лосяш проснулся рано утром со стойким ощущением, что он хочет поменять свою операционную систему "Окошки 95" на что-нибудь более современное, быстрое, надежное и максимально простое в эксплуатации. Лосяш он слышал немало лестных слов про операционную систему "Linux" от своего приятеля Пина, про которого даже ходили слухи, что он лично знаком с легендарным Tux'ом. Лосяш помчался к Пину, чтобы попросить его помочь с установкой Linux'а.

Пин очень обрадовался появлению Лосяша и его просьбе. Дело в том, что час назад у него докачался последний дистрибутив Slackware 11 и он хотел найти машину, на которой можно было бы с этим дистрибутивом поэксперементировать. Пин схватил DVD и уже собрался отправиться в путь, как вдруг вспомнил свой недавний разговор с Tux'ом, который сообщил ему, что при установке и дальнейшем использовании Slackware просто необходим шаманский бубен для подвешивания его над компьютером в строго горизонтальном положении. Бубен должен висеть на протяжении всей эксплуатации системы, чтобы обеспечить бесперебойную работу системы.

Шаманским бубном для установки Slackware является только такой бубен, который состоит из священных CD-дисков нулевого радиуса, но некоторого веса, со всеми предыдущими версиями Slackware, соединенных между собой невесомыми стержнями, пересекающимися и соединяющимися только под прямыми углами. Бубен связный, иначе это уже несколько бубнов. Бубен можно подвешивать на ниточке, привязанной к какому-нибудь одному его стержню. К счастью, у Пина уже есть такой бубен, только он не знает, можно ли его подвесить горизонтально. Пин просит Вас помочь ему, чтобы знать, сможет он использовать свой бубен, или придется покупать новый.

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

На первой строке входного файла записано число N - количество CD-дисков в бубне. На следующих N (N ≤ 10000 ) строках записываются числа X и Y (-10000 ≤ X, Y ≤ 10000) - координаты соответствующего диска, а также число L ( L ≤ 1000 ) - вес данного диска в каратах.
На следующей строке записано число M ( M ≤ 15000 ) - количество стержней. Далее на следующих M строках записаны номера дисков, соединенных соответствующим стержнем.

Все числа целые. Диски и стержни нумеруются с единицы.

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

Если подвешивание бубна возможно, выведите " YES " без кавычек. Иначе - " NO " (также без кавычек).

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

buben.in                 buben.out                
2
0 0 1
0 5 1
1
1 2
YES
3
0 0 5
1 0 5
0 1 5
2
1 2
1 3
NO
      

Задача M. Центральное отопление

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

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 800333-90-06*. Для простоты Пин решил купить простые батареи. Согласно таблице 14.1.3 этого ГОСТа, каждая батарея обогревает определённый объём воздуха - ровно K кубометров. Комната, которую собирается для своего друга обогреть Пин, имеет следующие размеры:

Определите, какое минимальное количество батарей Пину необходимо купить. Учтите только, что если в домике у Кар Карыча температура будет ниже, чем по ГОСТу, Кар Карыч никогда не поправится.

Входные данные
На единственной строке входного файла записано четыре целых числа: H, W, L, K. (H, W, L<=105, K<=2*109).

Выходные данные
На единственной строке выходного файла выведите ответ на задачу.


center.in                 center.out                
2 3 4 1 24
             

Всем успехов!