Задача A. Песочные часы

Автор:СПб 2005   Ограничение времени:2 сек
Входной файл:clocks.in   Ограничение памяти:64 Мб
Выходной файл:clocks.out  

Условие

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

Порывшись на чердаке, Петя нашел двое старых песочных часов — на a и на b минут соответственно. Каждые песочные часы состоят из двух половинок, одна из которых исходно заполнена песком.

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

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

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

Петя хочет узнать, как ему действовать, чтобы снять суп с плиты ровно через t минут.

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

Во входном файле заданы целые числа a, b и t.

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

Выведите последовательность инструкций для Пети. Каждая инструкция — это пара <событие>: <действие>. События бывают трех типов: Действия бывают четырех типов: Если подогреть суп с использованием этих песочных часов не удастся, выведите в выходной файл одно слово — «Impossible».

Ограничения

1 &le; a, b &le; 500, 1 &le; t &le; 105

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

Входной файл (clocks.in) Выходной файл (clocks.out)
1
5 7 9
Initially: flip A and B
When A stops: flip A
When B stops: flip A
When A stops: ready
2
2 4 11
Impossible

Задача B. K-числа

Автор:СПб 2005   Ограничение времени:2 сек
Входной файл:knumbers.in   Ограничение памяти:64 Мб
Выходной файл:knumbers.out  

Условие

Однажды мальчик Вася заметил, что номер его телефона 321321 и номер его дома 111 обладают интересным свойством: их можно разбить на несколько одинаковых частей: 321|321, 1|1|1. Вася назвал числа, которые можно разбить на k частей (k > 1), k-числами. Например, число 2323 является 2-числом (23|23), число 101010 — 3-числом (10|10|10), а число 222222 является одновременно 2-числом (222|222), 3-числом (22|22|22) и 6-числом (2|2|2|2|2|2). Васе интересно, много ли на свете таких интересных чисел, поэтому он просит вас написать программу, находящую количество k-чисел, не превосходящих заданное число n.

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

На первой строке входного файла задано число k, на второй — число n.

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

Выведите в выходной файл одно число — количество k-чисел, не превышающих n.

Ограничения

2 &le; k &le; 100, 1 &le; n &le; 10100

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

Входной файл (knumbers.in) Выходной файл (knumbers.out)
1
2
3140
31

Задача C. Восстановление строки

Автор:СПб 2005   Ограничение времени:2 сек
Входной файл:restore.in   Ограничение памяти:64 Мб
Выходной файл:restore.out  

Условие

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

Рассмотрим, что происходит при таком преобразовании со строкой &laquo;abraca&raquo;:

abraca &rarr;
abraca
bracaa
racaab
acaabr
caabra
aabrac
&rarr;
1: aabrac
2: abraca
3: acaabr
4: bracaa
5: caabra
6: racaab
&rarr; caraab

Итак, в результате мы получили строку &laquo;caraab&raquo;. В дополнение к найденной строке мы определяем также позицию исходной строки в отсортированном списке циклических сдвигов (в данном случае 2). Оказывается, что исходя из этих двух данных, первоначальная строка восстанавливается однозначно. Напишите программу, которая сделает это.

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

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

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

В выходной файл выведите исходную строку.

Ограничения

Длина заданной строки не превосходит 105.

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

Входной файл (restore.in) Выходной файл (restore.out)
1
2 
caraab
abraca
2
34 
eehnyollwwhvnewoeoriretdtdaaneanogb
whenwehavetolearntodowelearnbydoing
3
5 
bbccaabbaaaaaa
abacabaabacaba

Задача D. Робот

Автор:СПб 2005   Ограничение времени:2 сек
Входной файл:robot.in   Ограничение памяти:64 Мб
Выходной файл:robot.out  

Условие

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

Для того, чтобы добраться от одной комнаты до другой, в робота вводится программа  — последовательность цветов коридоров c1, c2,… , ck, по которым он должен пройти.

Робот выбирает коридор цвета c1, ведущий из комнаты, в которой он находится, и идет по нему до следующей комнаты. В следующей комнате он рассматривает все коридоры, кроме того, по которому он пришел, выбирает из них коридор цвета c2 и идет по нему до третьей комнаты, в которой выбирает коридор цвета c3 и так далее. При этом, если есть более одного коридора требуемого цвета или нет ни одного такого коридора, то у робота происходит ошибка и он ломается.

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

Если, находясь в комнате 1, робот получит программу &laquo;2 2 3&raquo;, то из комнаты 1 он сначала перейдет в комнату 3, затем в комнаты 5 и 6. Если же он получит программу &laquo;1 2 3&raquo; в комнате 4, то сначала он перейдет в комнату 3, а затем сломается, так как не сможет выбрать, по какому коридору ему идти дальше.

Ученые хотят построить центр управления в такой комнате, чтобы для любой другой комнаты A существовала корректная программа, получив которую, робот дойдет от центра управления до комнаты A.

Требуется написать программу, определяющую, в каких комнатах может находиться центр управления.

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

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

Первая строка входного файла содержит число n. Каждая из следующих n − 1 строк содержат по три числа: ai, bi, ci — описания коридоров, где ai и bi — номера комнат, соединяемых коридором, а ci — его цвет. Гарантируется что для любых двух комнат существует ровно один путь между ними.

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

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

Ограничения

1 &le; n &le; 105, 1&le; ai < bi&le; n, 1&le; ci&le; 105

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

Входной файл (robot.in) Выходной файл (robot.out)
1
6
1 3 2
5 6 3
3 4 1
1 2 1
3 5 2
1 2 5 6

0.261s 0.014s 21