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

Условие

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

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

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

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

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

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

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

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

• Initially — начальный момент времени, в последовательности должна быть ровно одна инструкция, помеченная этим событием, она должна быть первой;
• When A stops — когда заканчивает пересыпаться песок в первых часах;
• When B stops — когда заканчивает пересыпаться песок во вторых часах.

• flip A — перевернуть первые часы;
• flip B — перевернуть вторые часы;
• flip A and B — перевернуть и те и другие часы;
• ready — снять суп с плиты, инструкция с таким действием должна быть ровно одна, она должна быть последней.

Ограничения

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

5 7 9

Initially: flip A and B
When A stops: flip A
When B stops: flip A
When A stops: ready

2 4 11

Impossible

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

Условие

Однажды мальчик Вася заметил, что номер его телефона 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.

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

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

Ограничения

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

2
3140

31

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

Условие

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

Рассмотрим, что происходит при таком преобразовании со строкой «abraca»:

abraca
bracaa
racaab
acaabr
caabra
aabrac

1: aabrac
2: abraca
3: acaabr
4: bracaa
5: caabra
6: racaab

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

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

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

Ограничения

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

2 
caraab

abraca

34 
eehnyollwwhvnewoeoriretdtdaaneanogb

whenwehavetolearntodowelearnbydoing

5 
bbccaabbaaaaaa

abacabaabacaba

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

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

6
1 3 2
5 6 3
3 4 1
1 2 1
3 5 2

1 2 5 6