Каждый раз, приходя из школы, Петя разогревает себе суп.
Петя давно установил, что для достижения оптимальной температуры, суп
надо греть в течении ровно t минут. Однажды у Пети в часах села батарейка.
И тут неожиданно выяснилось, что это были единственные часы в доме.
Порывшись на чердаке, Петя нашел двое старых песочных
часов — на a и на b минут соответственно.
Каждые песочные часы состоят из двух половинок, одна из
которых исходно заполнена песком.
Для того, чтобы использовать часы, их ставят на одно
из оснований, при этом песок из верхней половины начинает
постепенно пересыпаться в нижнюю.
Песок пересыпается равномерно и с одинаковой скоростью, вне зависимости
от количества песка, оставшегося в верхней половине.
В первых часах весь песок пересыпается за a минут, во вторых — за
b минут.
В тот момент, когда Петя ставит суп на огонь, весь песок в каждых часах находится в
нижней половине. В этот момент Петя может перевернуть какие-либо часы, либо и те
и другие сразу. Далее Петя может переворачивать часы в момент, когда в одних
из них заканчивает пересыпаться песок. В один из таких моментов Петя должен
снять суп с плиты.
Петя хочет узнать, как ему действовать, чтобы снять суп с плиты ровно через
t минут.
Формат входного файла
Во входном файле заданы целые числа a, b и t.
Формат выходного файла
Выведите последовательность инструкций для Пети. Каждая инструкция — это пара
<событие>: <действие>.
События бывают трех типов:
Initially — начальный момент времени, в последовательности должна
быть ровно одна инструкция, помеченная этим событием, она должна быть первой;
When A stops — когда заканчивает пересыпаться песок в первых часах;
When B stops — когда заканчивает пересыпаться песок во вторых часах.
Действия бывают четырех типов:
flip A — перевернуть первые часы;
flip B — перевернуть вторые часы;
flip A and B — перевернуть и те и другие часы;
ready — снять суп с плиты, инструкция с таким действием должна
быть ровно одна, она должна быть последней.
Если подогреть суп с использованием этих песочных часов не удастся, выведите в
выходной файл одно слово — «Impossible».
Ограничения
1 ≤ a, b ≤ 500, 1 ≤ t ≤ 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
Однажды мальчик Вася заметил, что номер его телефона 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.
В одном алгоритме сжатия используется преобразование строк, суть которого состоит
в следующем. Рассмотрим некоторую строку. Возьмем все ее возможные циклические сдвиги
и расположим их в словарном порядке в виде квадратной таблицы. В получившейся таблице выделим
последний столбец, который, если его записать в виде строки, и будет являться результатом
описанного преобразования.
Рассмотрим, что происходит при таком преобразовании со строкой «abraca»:
Итак, в результате мы получили строку «caraab». В дополнение к найденной строке мы
определяем также позицию исходной строки в отсортированном списке циклических сдвигов (в
данном случае 2). Оказывается, что исходя из этих двух данных, первоначальная строка
восстанавливается однозначно. Напишите программу, которая сделает это.
Формат входного файла
В первой строке входного файла записано целое число k — номер исходной строки в отсортированном
списке циклических сдвигов. На следующей строке записан результат преобразования. Входные данные
таковы, что исходная строка всегда существует. Сама строка состоит из символов с кодами
от 33 до 255.
В Пентагоне испытывают новый тип роботов. Испытания проводятся на полигоне,
представляющем собой n комнат, соединенных цветными коридорами так, что
между любыми двумя комнатами существует ровно один путь.
Для того, чтобы добраться от одной комнаты до другой, в робота вводится программа — последовательность цветов коридоров c1, c2,… , ck, по которым он должен пройти.
Робот выбирает коридор цвета c1, ведущий из комнаты, в которой он находится,
и идет по нему до следующей комнаты. В следующей комнате он рассматривает все
коридоры, кроме того, по которому он пришел, выбирает из них коридор цвета c2 и
идет по нему до третьей комнаты, в которой выбирает коридор цвета c3 и так далее.
При этом, если есть более одного коридора требуемого цвета или нет ни одного такого
коридора, то у робота происходит ошибка и он ломается.
На рисунке приведен пример схемы полигона, на которой комнаты обозначены кружками,
коридоры — линиями, а цвета коридоров — цифрами на линиях.
Если, находясь в комнате 1, робот получит программу «2 2 3», то из комнаты 1 он
сначала перейдет в комнату 3, затем в комнаты 5 и 6. Если же он получит программу
«1 2 3» в комнате 4, то сначала он перейдет в комнату 3, а затем сломается, так
как не сможет выбрать, по какому коридору ему идти дальше.
Ученые хотят построить центр управления в такой комнате, чтобы для любой другой
комнаты A существовала корректная программа, получив которую, робот дойдет от центра
управления до комнаты A.
Требуется написать программу, определяющую, в каких комнатах может находиться центр управления.
В приведенном примере центр управления может находиться в любой из комнат, кроме третьей и
четвертой.
Формат входного файла
Первая строка входного файла содержит число n. Каждая из следующих n − 1 строк содержат
по три числа: ai, bi, ci — описания коридоров,
где ai и bi — номера комнат, соединяемых коридором, а ci — его цвет.
Гарантируется что для любых двух комнат существует ровно один путь между ними.
Формат выходного файла
Выведите в выходной файл номера комнат, в которых может располагаться командный центр.
Номера должны быть упорядочены в возрастающем порядке.
Ограничения
1 ≤ n ≤ 105,
1≤ ai < bi≤ n,
1≤ ci≤ 105
Если, находясь в комнате 1, робот получит программу «2 2 3», то из комнаты 1 он
сначала перейдет в комнату 3, затем в комнаты 5 и 6. Если же он получит программу
«1 2 3» в комнате 4, то сначала он перейдет в комнату 3, а затем сломается, так
как не сможет выбрать, по какому коридору ему идти дальше.