| horatio.in
|
horatio.out
|
thehereditarydukeofdanishlandslaertthesonofpoloniy
|
aertthesonofpoloniythehereditarydukeofdanishlandsl
|
|
|
Задача D. Два могильщика
Имя входного файла: music.in
Имя выходного файла: music.out
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Mb
|
Из беседы Гамлета с Горацио: "У этого малого что, никакого
уважения к своему делу? Поет себе и роет могилу!"
Эти слова Гамлета услышали оба могильщика и клятвенно решили
выполнять следующее:
- Если принцу Гамлету не нравится, то больше не петь за работой.
- Не бросать свои музыкальные занятия, но далее
заниматься музыкой только в перерывах между работой.
- Развивать и совершенствовать свои музыкальные способности.
- Повысить свою музыкальную квалификацию и научиться
аккомпанировать на лютне.
Один из могильщиков довольно хорошо разбирается в музыке и
решил научить второго могильщика профессиональной игре на лютне
с использованием аккордов:
-
Известно, что в музыке существует 12 нот. Расстояние между двумя
нотами называется полутоном.
- Названия нот в данной задаче в порядке следования от ноты с номером 0
до ноты с номером 11:
C C# D D# E F F# G G# A A# B
-
Аккорд - это сочетание нескольких нот, причём одна из них называется тоника.
Запись аккорда заключается в указании тоники и того, на сколько отстоят от неё
остальные ноты в этом аккорде.
-
Для простоты первый могильщик ведет обучение в предположении,
что все ноты цикличны, т.е. после последней снова идёт первая.
-
Существуют следующие аккорды (в используемых
нотах указаны интервалы в полутонах в сторону
повышения от тоники тех нот, которые должны
использоваться, все самостоятельные
единицы в записи аккорда разделяются пробелом):
- Мажорный аккорд
Запись: указывается только тоника.
Используемые ноты: 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 обитателей
Эльсинора. Главное, в его пьесе будет одна очень страшная тайна,
которую еще никто не знает.
(Эту тайну Марцелл еще не придумал, так как настоящую тайну про тень
отца Гамлета Марцел никогда и никому не расскажет!)
Он решил, что акт пьесы будет интересен, если в нем:
- кто-то узнаёт тайну;
- кто-то узнаёт, что кто-то не знает тайну;
- кто-то узнаёт, что кто-то знает тайну.
Кроме того, два подряд акта одного типа слишком скучны. Например,
если в первом акте Гамлет узнает, что Клавдий не знает тайну, а во
втором Офелия узнает, что Гертруда не знает тайну, то читать пьесу
станет неинтересно.
Теперь Марцелл озаботился вопросом, какое максимальное количество актов
может быть в его пьесе при условии, что все акты интересны, и читать
пьесу не скучно. Помогите ему!
Входные данные
В первой строке входного файла находится число 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
|
