Гамлет, принц Датский

      
A. Сарафан для призрака датского короля
B. Лаэрт в затруднении
C. Загадка Горацио
D. Два могильщика
E. Полоний и его коллекция
F. Часы для Офелии
G. Пьеса от Марцелла
H. Быть или не быть?
                    
      

Задача A. Сарафан для призрака датского короля

Имя входного файла: phantom.in
Имя выходного файла: phantom.out
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Mb
Однажды призрак короля датского решил изобразить привидение по всем канонам этого дела. Как Вы знаете, для этого ему понадобились: хриплый голос, ржавые гремящие цепи, белый сарафан и зловещий смех. Цепи ему обещал одолжить призрак короля шведского, весьма опытный в подобных делах. С хриплым голосом и зловещим смехом проблем не возникло. Но где же взять сарафан? К счастью, во время очередного наблюдения за сыном своим Гамлетом, призрак взглянул во внутренний дворик - и, о чудо! - увидел вожделенный сарафан. Он сушился на бельевой веревке во дворе. Быстро оценив ситуацию, тень отца Гамлета решила не медлить, заметила еще одну веревку, и сейчас же спустилась на нее.

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

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

Входной файл содержит пять строк.

  1. шесть чисел x11,y11,z11,x12,y12,z12 - координаты точек первой прямой
  2. шесть чисел x21,y21,z21,x22,y22,z22 - координаты точек второй прямой
  3. три числа a1,b1,c1 - координаты сарафана
  4. три числа a2,b2,c2 - координаты призрака короля датcкого
  5. одно число v - скорость призрака в передничке.
Все числа - целые, не превышающие по модулю 1000000. Гарантируется, что и сарафан, и передник находятся каждый на одной из веревок.

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

Минимальное время, необходимое призраку, чтобы добраться до сарафана. Результат выведите с пятью знаками после десятичной точки. Если призрак добраться до сарафана не сможет, выведите в выходной файл число "-1".

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

phantom.in                 phantom.out                
0 0 0 5 5 5
6 6 6 9 9 9
0 0 0
10 10 10
1
17.32051
      

Задача B. Лаэрт в затруднении

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

Лаэрт составил иерархию подчиненности в королевстве, что оказалось очень несложно, ибо ее можно изобразить в виде дерева: у каждого вассала, кроме короля, есть ровно один непосредственный сеньор и, возможно, несколько подчинённых вассалов. Ваша задача - по данной структуре иерархии в королевстве Клавдия составить оптимальный список участников турнира.

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

В первой строке входного файла находится число N - количество рыцарей Датского королевства (1 ≤ N ≤ 100000). В следующих N - 1 строках содержится по два числа ai и bi (1 ≤ ai, bi ≤ N), разделённых пробелом: ai - номер рыцаря, являющегося сеньором рыцаря с номером bi. Клавдий имеет номер 1, и тоже может участвовать в турнире.

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

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

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

laertes.in                 laertes.out                
6
1 2
1 3
2 4
4 5
3 6
3
1 2
4 5
3 6
      

Задача C. Загадка Горацио

Имя входного файла: horatio.in
Имя выходного файла: horatio.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 Mb
      
В юности Горацио увлекался составлением полных геральдических имен. А дело это нешуточное - ошибешься где, моментально какой-нибудь герцог отправит прямиком за Йориком. Правила достаточно просты: герцог называет Горацио свой родовой титул, а Горацио находит его лексикографически минимальный циклический сдвиг. Не всякий в датском королевстве может это сделать!

Но теперь Горацио уже не к лицу такие несерьезные занятия, и ему нужен преемник. Попробуйте себя в этом деле!

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

Файл исходных данных содержит единственную строку - родовой титул герцога, состоящий из строчных латинских букв, длиной не более 100000 символов.

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

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

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

horatio.in                 horatio.out                
thehereditarydukeofdanishlandslaertthesonofpoloniy
aertthesonofpoloniythehereditarydukeofdanishlandsl
      

Задача D. Два могильщика

Имя входного файла: music.in
Имя выходного файла: music.out
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Mb
Из беседы Гамлета с Горацио: "У этого малого что, никакого уважения к своему делу? Поет себе и роет могилу!"

Эти слова Гамлета услышали оба могильщика и клятвенно решили выполнять следующее:

  • Если принцу Гамлету не нравится, то больше не петь за работой.
  • Не бросать свои музыкальные занятия, но далее заниматься музыкой только в перерывах между работой.
  • Развивать и совершенствовать свои музыкальные способности.
  • Повысить свою музыкальную квалификацию и научиться аккомпанировать на лютне.
Один из могильщиков довольно хорошо разбирается в музыке и решил научить второго могильщика профессиональной игре на лютне с использованием аккордов:

  1. Известно, что в музыке существует 12 нот. Расстояние между двумя нотами называется полутоном.
  2. Названия нот в данной задаче в порядке следования от ноты с номером 0 до ноты с номером 11:
    C C# D D# E F F# G G# A A# B
  3. Аккорд - это сочетание нескольких нот, причём одна из них называется тоника. Запись аккорда заключается в указании тоники и того, на сколько отстоят от неё остальные ноты в этом аккорде.
  4. Для простоты первый могильщик ведет обучение в предположении, что все ноты цикличны, т.е. после последней снова идёт первая.
  5. Существуют следующие аккорды (в используемых нотах указаны интервалы в полутонах в сторону повышения от тоники тех нот, которые должны использоваться, все самостоятельные единицы в записи аккорда разделяются пробелом):
    • Мажорный аккорд
      Запись: указывается только тоника.
      Используемые ноты: 0, 4, 7
      Пример: C
    • Минорный аккорд
      Запись: указывается только тоника и символ "m"
      Используемые ноты: 0, 3, 7
      Пример: C m
    • Большой септаккорд
      Запись: сначала идёт запись мажорного или минорного (в используемых нотах это показано с помощью записи "4(3)" ) септаккорда, а затем "7+"
      Используемые ноты: 0, 4(3), 7, 11
      Примеры: C 7+, C m 7+
    • Доминантсептаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "7"
      Используемые ноты: 0, 4(3), 7, 10
      Примеры: C 7, C m 7
    • Секстаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "6"
      Используемые ноты: 0, 4(3), 7, 9
      Примеры: C 6, C m 6
    • Увеличенный квинтаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "5+"
      Используемые ноты: 0, 4(3), 7, 8
      Примеры: C 5+, C m 5+
    • Уменьшенный квинтаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "5-"
      Используемые ноты: 0, 4(3), 7, 6
      Примеры: C 5-, C m 5-
    • Квартаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "4"
      Используемые ноты: 0, 4(3), 7, 5
      Примеры: C 4, C m 4
    • Секундаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "2"
      Используемые ноты: 0, 4(3), 7, 2
      Примеры: C 2, C m 2
    • Малый вводный септаккорд
      Запись: сначала указывается тоника, а затем "dim"
      Используемые ноты: 0, 3, 6, 9
      Пример: C dim
    • Большой нонаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "9"
      Используемые ноты: 0, 4(3), 7, 11, 2
      Примеры: C 9, C m 9
    • Большой ундецимаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "11"
      Используемые ноты: 0, 4(3), 7, 11, 2, 5
      Примеры: C 11, C m 11
    • Большой терцдецимаккорд
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "13"
      Используемые ноты: 0, 4(3), 7, 11, 2, 5, 9
      Примеры: C 13, C m 13
    • Увеличенное трезвучие
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "aug"
      Используемые ноты: 0, 4(3), 8
      Примеры: C aug, C m aug
    • Уменьшенное трезвучие
      Запись: сначала идёт запись мажорного или минорного септаккорда, а затем "-"
      Используемые ноты: 0, 4(3), 6
      Примеры: C -, C m -
    • Power Chords аккорды
      Запись: сначала идёт запись тоники, а затем "5"
      Используемые ноты: 0, 7
      Пример: C 5
    • Трезвучие с задержанной II ступенью
      Запись: сначала идёт запись тоники, а затем "sus2"
      Используемые ноты: 0, 2, 7
      Пример: C sus2
    • Трезвучие с задержанной IV ступенью
      Запись: сначала идёт запись тоники, а затем "sus4"
      Используемые ноты: 0, 5, 7
      Пример: C sus4

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

  • На грифе лютни есть N ладов и 6 струн. Лад - это место, где можно зажать струну, чтобы изменить её звучание.
  • Каждая струна издаёт сама по себе какую-то ноту. Чтобы повысить звучание ноты на x полутонов надо зажать её на ладе номер x.

Помогите несчастному второму могильщику решить задачку, которую ему задал первый могильщик! А потребовал он для заданного аккорда найти все способы постановки. Необходимо следовать следующим правилам:

  • Каждая нота должна играться хотя бы на одной струне
  • Каждая струна должна издавать одну из нот аккорда или не звучать вовсе
  • Вы можете каждым пальцем зажать (или не зажимать) какую-либо струну.
  • Расстояние между самым левым и самым правым пальцем не должно превышать три лада.
В качестве расстояния следует понимать разность между номерами зажатых ладов. Каждый аккорд выводится как последовательность из шести символов - по одному на каждую струну. символ "0" означает, что струна не зажата. Символы "1".."9" используются для обозначения зажатого лада с наибольшим номером. Символ "x" означает, что данная струна не используется в аккорде. Сгенерируйте все возможные способы постановки аккорда и выведите их по одному в строке.

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

Во входном файле три строки. В первой строке указано N - количество ладов (0 ≤ N ≤ 9). Во второй строке через пробел перечислены ноты, которые струны издают, если никакой лад на них не зажат. В третьей строке указан аккорд в формате, описанном выше.

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

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

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

music.in                 music.out                
0
C C C C C G
C 5
xxxx00
xxx0x0
xxx000
xx0xx0
xx0x00
xx00x0
xx0000
x0xxx0
x0xx00
x0x0x0
x0x000
x00xx0
x00x00
x000x0
x00000
0xxxx0
0xxx00
0xx0x0
0xx000
0x0xx0
0x0x00
0x00x0
0x0000
00xxx0
00xx00
00x0x0
00x000
000xx0
000x00
0000x0
000000
      

Задача E. Полоний и его коллекция

Имя входного файла: polonius.in
Имя выходного файла: polonius.out
Ограничение по времени: 3 секунды
Ограничение по памяти: 64 Mb
Полоний - первый вельможа короля Клавдия - известный коллекционер в Датском королевстве. Но он не увлекается всякой ерундой, как монеты, картины, скульптуры, драгоценности и прочие никому не нужные вещи. Его коллекция - сугубо практическая! Она состоит из маленьких и больших, стеклянных и глиняных, прозрачных и матовых сосудов с ядами. Скоро их уже будет более полутысячи!

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

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

Рассмотрим пример. Пусть флакончики стоят в порядке 5, 2, 4, 1, 3. Тогда, взяв в руки флакончики 2, 4, 1, и выполнив одну операцию, Полоний может получить одну из следующих последовательностей ядов:

2, 4, 1, 5, 3
5, 2, 4, 1, 3
5, 3, 2, 4, 1.
А сможете ли вы упорядочить яды, как это делает Полоний?

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

В первой строке входного файла находится одно число n (5 ≤ n ≤ 500) - количество бутыльков. Во второй строке записаны n различных чисел от 1 до n - ярлычки на бутыльках в порядке, в котором они стоят на полке у Полония.

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

В первую строку выведите K - количество операций (не обязательно минимальное, но не более 3*n*(n-1)/2) для упорядочивания ядов. В каждую из последующих K строк выведите описание одной операции в формате "I J", где I - позиция в последовательности ядов, с которой начинается перемещаемая часть, и J - позиция, после которой она вставляется. Если бутыльки вставляются в начало, то J = 0.

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

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

Задача F. Часы для Офелии

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

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

На часах есть 4 кнопки: "+", "-", "h", "m". Чтобы перевести часы на час вперед, необходимо при нажатой кнопке "+" нажать кнопку h. Аналогичны комбинации "+m", "-h", "-m".

Гамлет не хочет, чтобы кнопки на подарке были истерты раньше времени, поэтому Офелии надо выполнить минимальное количество нажатий на кнопки. И вот теперь перед Офелией стоит Гамлетовский вопрос: "Давить или не давить? А если давить, то сколько раз? Какое минимальное число нажатий необходимо сделать, чтобы поставить правильное время?"

Пусть, например, на часах Офелии установлено время 00:00, а текущее время 01:01. Тогда достаточно трех нажатий: нажимаем + и, не отпуская его, нажимаем h и m.

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

В первой строке входного файла задано текущее время на часах в формате HH:MM. Во второй строке в таком же формате - время, которое необходимо установить.

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

Выведите в выходной файл единственное число - минимальное количество нажатий.

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

ophelia.in                 ophelia.out                
00:00
01:01
3
      

Задача G. Пьеса от Марцелла

Имя входного файла: marcellus.in
Имя выходного файла: marcellus.out
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Mb
      
Однажды у стен королевского замка Марцелл поклялся Гамлету не разглашать тайну появления призрака. Тайна жгла Марцелла. А клятва принуждала молчать. Наконец Марцелл, устав и от клятвы молчания, и от военных забот, решил на досуге заняться творчеством. И взор его обратился на такую область человеческого гения, как пьесы.

Марцелл задумал сочинить самую длинную пьесу про всех n обитателей Эльсинора. Главное, в его пьесе будет одна очень страшная тайна, которую еще никто не знает. (Эту тайну Марцелл еще не придумал, так как настоящую тайну про тень отца Гамлета Марцел никогда и никому не расскажет!) Он решил, что акт пьесы будет интересен, если в нем:

  1. кто-то узнаёт тайну;
  2. кто-то узнаёт, что кто-то не знает тайну;
  3. кто-то узнаёт, что кто-то знает тайну.
Кроме того, два подряд акта одного типа слишком скучны. Например, если в первом акте Гамлет узнает, что Клавдий не знает тайну, а во втором Офелия узнает, что Гертруда не знает тайну, то читать пьесу станет неинтересно.

Теперь Марцелл озаботился вопросом, какое максимальное количество актов может быть в его пьесе при условии, что все акты интересны, и читать пьесу не скучно. Помогите ему!

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

В первой строке входного файла находится число n (1 ≤ n ≤ 100) - количество обитателей Эльсинора. В последующих n строках - их имена по одному в строке.

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

В первую строку выходного файла выведите максимальное количество актов. В каждой последующей строке выведите описание очередного акта:

  • < name > finds out the secret
    - житель < name > узнает тайну в этом акте;
  • < name1 > finds out that < name2 > knows the secret
    - житель < name1> узнает, что житель < name2 > знает тайну;
  • < name1 > finds out that < name2 > doesn't know the secret
    - житель < name1 > узнает, что житель < name2 > не знает тайну.

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

    marcellus.in                 marcellus.in.out                
    2
    Hamlet
    Ophelia
    
    6
    Ophelia finds out that Hamlet doesn't know the secret
    Hamlet finds out the secret
    Ophelia finds out that Hamlet knows the secret
    Hamlet finds out that Ophelia doesn't know the secret
    Ophelia finds out the secret
    Hamlet finds out that Ophelia knows the secret
    

    Задача H. Быть или не быть?

    Имя входного файла: toBeOrNotToBe.in
    Имя выходного файла: toBeOrNotToBe.out
    Ограничение по времени: 1 секунда
    Ограничение по памяти: 64 Mb
          
    "Быть или не быть? Вот в чем вопрос!" - этот вопрос Гамлет задавал всем, кто встречался ему во дворце. Ответ Гамлет записывал в специальную книжечку, которую никому не показывал. Однажны Горацио увидел записи в этой книжечке и был поражен. Оказывается, Гамлет ставил ответы на плане дворца, отмечая в каждой комнате ответ, который он получал. Понятно, что на вопрос "Быть или не быть?" Гамлет получал только ответы "Да" или "Нет". Для краткости Гамлет ставил единички или нолики в соответствии с тем, ответ "Да" или "Нет" он получал.

    Рассматривая план, Горацио обнаружил, что план дворца представляет собой квадрат N*N комнат, причем в любом квадрате размера KxK было ровно S ответов "Да", закодированных единицами. Единиц было маловато...

    Горацио - настоящий друг Гамлета - решил, что единиц на плане должно быть намного больше. Он даже решил, какое значение S поднимет настроение Гамлета. Это число он знает, а вот как расставить единицы на плане - понять не может. Помогите Горацио!

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

    Во входном файле записаны три целых числа N, K, S (1 ≤ N ≤ 100, 1 ≤ K ≤ N, 0 ≤ S ≤ K2).

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

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

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

    toBeOrNotToBe.in                 toBeOrNotToBe.out                
    3 2 1
    0 0 0
    0 1 0
    0 0 0
    4 2 2
    1 0 0 1
    0 1 1 0
    1 0 0 1
    0 1 1 0

    vvv