Задача A. Down the Rabbit Hole

Задача A. Down the Rabbit Hole

Имя входного файла:	a. in
Имя выходного файла:	a. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

Алиса вернулась к столику, смутно надеясь найти там еще один ключ или, по крайней мере, книгу, объясняющую, как человеку научиться складываться подобно подзорной трубе; но на этот раз она обнаружила на столике пузырек ("которого здесь точно не было прежде", - сказала Алиса), и на горлышке пузырька был бумажный ярлык со словами "ВЫПЕЙ МЕНЯ", красиво напечатанными большими буквами.

Это, конечно, легко было сказать - "Выпей меня", но умненькая Алиса не собиралась так сразу следовать подобному совету; "Нет, я сперва посмотрю, - сказала она, - есть тут надпись "Яд" или нет".

Однако на этом пузырьке не было надписи "Яд", так что Алиса решилась отведать его содержимое, и оно ей очень понравилось (на вкус это было как смесь вишневого пирога, сладкого омлета, ананаса, жареной индейки, конфет и горячих гренок с маслом) - так что она быстро выпила все до капли.

"Какое странное чувство! - воскликнула Алиса, - Я, должно быть, складываюсь, как подзорная труба!"[*]

В стране чудес есть два способа изменить свой рост. Выпив бутылочку, на которой написано “Выпей меня”, Алиса уменьшается на a/b часть от своего текущего роста. Съев пирожок, на котором написано “Съешь меня”, Алиса увеличивается на с/d от своего текущего роста. Алиса хочет узнать: существует ли такая непустая последовательность съедания пирожков и выпивания бутылочек, что в конце этой последовательности Алиса вновь вернется к первоначальному росту. Если такие последовательности существуют, Алиса хочет выбрать из них ту, длина которой минимальна.

Формат входных данных

В первой строке входного файла через пробел записано два целых положительных числа a и b (a < b ≤ 10000). Во второй строке входного файла через пробел записано два целых положительных числа c и d (c, d ≤ 10000).

Формат выходных данных

Если требуемой последовательности съеданий пирожков и выпиваний бутылочек не существует, то в единственную строку выходного файла необходимо вывести -1. В противном случае в первой строке необходимо вывести одно число N – общее количество пирожков и бутылочек в последовательности. В следующих N строках необходимо вывести описание искомой последовательности съеданий пирожков и выпиваний бутылочек в следующем виде: в каждой строке должно быть выведено единственное слово “EAT” или “DRINK” (без кавычек). Слово “EAT” соответствует съедаемому пирожку, а слово “DRINK” – выпиваемой бутылочке. Если существует несколько последовательностей одинаковой минимальной длины, удовлетворяющих условию задачи, вывести любую из них.

Примеры

a. in	a. out
1 3 1 2	2 DRINK EAT
1 2 1 2	-1

Задача B. Advice from a Caterpillar

Имя входного файла:	b. in
Имя выходного файла:	b. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

- Но я не змея, говорю же вам! - сказала Алиса. - Я...

- Ну и? Что же ты такое? - осведомилась Голубка. - Вижу, ты пытаешься что-то придумать!

- Я... Я девочка, - произнесла Алиса не слишком уверенно, ибо помнила, через сколько превращений прошла в этот день.

- Ну разумеется! - воскликнула Голубка тоном глубочайшего презрения. - Я повидала достаточно девочек на своем веку, но ни одной с такой шеей, как эта! Нет, нет! Ты змея; и отрицать это бесполезно. Ты, пожалуй, теперь еще заявишь, что никогда не пробовала яиц!

- Я пробовала яйца, разумеется, - сказала Алиса, которая была очень правдивым ребенком, - но девочки, знаете ли, едят яйца, как и змеи.

- Я этому не верю, - сказала Голубка, - но если они это делают, значит, они тоже - разновидность змей, вот и все, что я могу сказать![*] С этими словами Голубка улетела обратно к себе в гнездо, устроенное в дупле высокого старого дуба.

“Ну уж нет,” - подумала про себя Алиса – “с каких это пор птицы стали вместо неё решать, кто она – девочка или змея! Сейчас бы только добраться до её гнезда…”

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

Гнездо Голубки расположено в дупле старого дуба, находящемся на высоте H от земли. Сам дуб представляет собой прямой круглый цилиндр с диаметром основания D. Алиса хочет, оставаясь ногами на земле, дотянуть голову до гнезда Голубки, при этом сделав как можно больше полных оборотов шеей вокруг ствола дуба. Длина шеи Алисы равна L. Толщиной шеи Алисы и размерами остальных частей тела пренебречь.

Формат входных данных

Во входном файле записано три натуральных числа H, D и L, разделенные одним или несколькими пробелами и символами переноса строки (0 < H, D, L ≤ 1000).

Формат выходных данных

В выходной файл выведите единственное целое число – максимально возможное полное число оборотов Алисы вокруг дуба. Выведите -1 в случае, если Алиса не сможет дотянуться до гнезда Голубки.

Примеры

b. in	b. out
1 1 10	3
10 1 9	-1

Задача C. A Mad Tea-Party

Имя входного файла:	c. in
Имя выходного файла:	c. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

- А теперь – десерт! - громко провозгласил Шляпник.

- Что у нас на десерт? - спросила Соня.

Шляпник выдержал небольшую паузу, а затем полушепотом произнес: “Торт!”. Вся ненормальная троица разом посмотрела на Алису.

- Что-то не так? – вежливо осведомилась Алиса.

- Ты же не будешь есть торт? – уточнил Шляпник.

Такая постановка вопроса задела Алису. “Почему нет?” - возразила она.

- Неужели ты имеешь в виду, что ты действительно хочешь торт? – переспросил Мартовский заяц, выуживая свой хронометр из чашки с чаем.

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

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

- А где же торт? – спросила Алиса.

Воцарилось неловкое молчание. Шляпник выразительно посмотрел на Алису и, наконец, указал пальцем на нарисованный треугольник: - Вот же он, перед тобой! И тебе придется его разрезать!

- Почему мне? Я же даже не буду его есть? – Алиса вконец растерялась.

Потому что мы не можем его резать - грустно сказала Соня. - Если будет резать кто-то из нас, он обязательно отрежет себе кусок больше, чем другим. А ты, как незаинтересованное лицо, сможешь разрезать торт так, чтобы все куски были одинаковыми.

Алисе понравилось, что её назвали незаинтересованным лицом, однако она понятия не имела, каким же образом правильно разрезать торт.

«Все, что тебе нужно – это пр-р-р-осто найти сер-р-р-едину тор-р-рта» - промурчал голос над ухом.

- Чешир! - обрадовалась Алиса.

«А потом-м-м» - продолжил голос, с явным удовольствием потягивая каждую попадающуюся ему букву Р – «сделать пр-р-рямые р-р-разр-р-резы до каждой из вер-р-ршин. И, кстати, та изогнутая штука называется тр-р-ранспор-р-р-тир-р-р-р-ром-м-м-м-м.»

На плоскости координатами своих трех вершин задан треугольник ABC. Чтобы разделить торт на 3 равные по площади части, Алисе требуется найти координаты точки Z внутри треугольника, такой, что площади треугольников ZAB, ZBC и ZCA равны.

Формат входных данных

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

Формат выходных данных

В выходной файл через пробел выведите два числа X и Y: искомые координаты точки Z. Отличие вашего ответа от правильного не должно превышать 10-5.

Пример

c. in	c. out
0 0 0 6 6 0	2.000

Задача D. The Queen’s Croquet Ground

Имя входного файла:	d. in
Имя выходного файла:	d. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

Поначалу труднее всего для Алисы оказалось управляться со своим фламинго; ей удалось довольно удобно пристроить его туловище у себя под мышкой (его ноги при этом свисали сзади), но, стоило ей выпрямить ему шею и замахнуться для удара его головой по ежу, как фламинго изгибал шею и заглядывал ей в лицо с таким удивленным выражением, что Алиса не могла сдержать взрыва смеха. Когда же она направляла его голову вниз, и снова готова была бить, то с раздражением убеждалась, что еж успел развернуться и трусит себе прочь. Ко всему прочему, на пути, по которому она собиралась послать ежа, как правило, оказывалась складка или борозда, и согнутые солдаты все время поднимались и переходили с места на место, так что Алиса быстро пришла к заключению, что это воистину очень сложная игра. [*]

Наконец, Алиса исхитрилась справиться со своим фламинго, не теряя при этом из виду ежа, и нанести прицельный удар. Результат оказался неожиданным – вместо того, чтобы покатиться в направлении удара, ёж неторопливо отполз на пару футов в сторону и отчетливо произнес «Ай-ай-ай».

- Что случилось? – спросила Алиса.

- Кажется, я потянул себе косолапую мышцу – заявил Ёж и добавил: - А все из-за того, что у тебя совершенно не поставлена техника удара!

- Извините – сказала Алиса, - я не нарочно. Могу я чем-нибудь помочь?

- Разумеется. Теперь тебе придется отнести меня к Вегетеринару.

- К Веге… кому?

- К Вегетеринару. Только сначала занеси меня в мое гнездо, мне нужно захватить веер и ведерко.

Алиса почувствовала, что теряет нить рассуждений Ежа, и предприняла последнюю отчаянную попытку поймать смысл происходящего: - Веер и ведерко? Зачем?

- Как зачем? – Ежу, кажется, начали надоедать глупые вопросы Алисы – А что обо мне подумают соседи, если я заявлюсь в Вегетеринару без веера и ведерка? Да, и еще – добавил Ёж – разумеется, ты должна помнить, что по пути к Вегетеринару по каждой дорожке тебе можно будет проходить не более чем по одному разу! А теперь – пошли скорее, пока Королева нас не заметила и не велела отрубить тебе голову!

Королевский Парк состоит из нескольких лужаек, соединенных между собой дорожками. Любая пара лужаек может быть соединена не более чем одной дорожкой. На одной из этих лужаек идет игра в Королевский Крокет, на другой – расположен домик Вегетеринара, на третьей находится гнездо Ежа. Алисе требуется дойти от лужайки, где идет игра в Крокет, до гнезда Ежа, а оттуда – до домика Вегетеринара. При этом Алисе строго запрещено проходить по любой из дорожек Парка более одного раза (однако, она может проходить несколько раз через одни и те же лужайки; в том числе, Алиса может пройти мимо домика Вегетеринара по пути к гнезду Ежа).

Формат входных данных

В первой строке входного файла указаны через пробел два числа N (3≤N≤100) - количество лужаек в Королевском Парке, M(0≤M≤N*(N-1)/2) - количество дорожек. Все лужайки Парка занумерованы от 1 до N. Во второй строке входного файла указаны три числа A, B,C (1≤A, B,C≤N) - номера лужаек, на которых соответственно: (A) проходит игра в Крокет, (B) расположен домик Вегетеринара, (C) находится гнездо Ежа. Далее следует M строк входного файла, описывающих дорожки парка. Каждая из этих строк описывает одну дорожку и содержит два целых числа – номера двух лужаек, соединяемых дорожкой. Номер первой лужайки всегда меньше номера второй. Гарантируется, что между любой парой лужаек есть не более одной дорожки.

Формат выходных данных

Если путь по Королевскому Парку, удовлетворяющий условию задачи, существует, то в первой строке выходного файла нужно вывести количество лужаек T, по которым проходит этот путь (включая начальную и конечную лужайки пути). Во второй строке должны быть указаны через пробел T чисел – номера лужаек, по которым проходит путь (в прямой последовательности). Если существует несколько решений задачи, вывести любое.

Если пути по Королевскому Парку, удовлетворяющего условию задачи, не существует, в выходной файл записать единственное число: -1.

Примеры

d. in	d. out
3 2 1 3 2 1 2 2 3	3 1 2 3
3 2 2 3 1 1 2 2 3	-1

Задача E. The Lobster Quadrille

Имя входного файла:	e. in
Имя выходного файла:	e. out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

Якобы Черепаха тяжело вздохнул и вытер ластой глаза. Он взглянул на Алису и попытался заговорить, но минуту или две рыдания душили его. "Словно ему кость в горло попала", - сказал Грифон и принялся трясти его и хлопать по спине. В конце концов голос вернулся к Якобы Черепахе, и, со слезами, стекавшими по щекам, он продолжил рассказ:

- Ты, может быть, не жила достаточно долго на дне морском ("Не жила", - сказала Алиса), и тебя, возможно, ни разу не представляли Омару (Алиса начала было: "Однажды я пробовала..." - но поспешно прикусила язык и сказала: "Нет, никогда") - так что ты и понятия не имеешь, какая восхитительная вещь Омаровая Кадриль!

- И впрямь, - призналась Алиса. - А что это за танец?

- Ну, - сказал Грифон, - первым делом…[*]

Первым делом надо выбрать медленную музыку для танца – всхлипнул Якобы Черепаха. Обычно Омаровую Кадриль танцуют на десять семнадцатых, но, в крайнем случае, подойдет и одна пятая (“Одна пятая чего?” - попыталась уточнить Алиса, но Якобы Черепаха проигнорировал вопрос).

- Когда музыка выбрана, все участники выстраиваются в Омаровую Колонну.

- Правильно выстроиться в Омаровую Колонну очень важно – подтвердил Грифон.

- Да, это самое важное в танце! Почти такое же важное, как вовремя сказать «Спасибо», когда во сне разговариваешь сам с собой! – подтвердил Якобы Черепаха. – Колонна строится по следующему правилу: первый и второй ряды колонны состоят из одного омара каждый. В любом следующем ряду колонны число омаров равно сумме числа омаров в двух предыдущих рядах колонны, взятой по модулю M.

- Как видишь, на самом деле все очень просто – заметил Грифон. - Вот только у омаров случаются проблемы с устным счетом. И кому-нибудь приходится проверять, правильно ли они выстроились в колонну.

- Неужели вы пересчитываете их всех? – спросила Алиса.

- А кто тебе сказал, что их пересчитываем МЫ? – хором воскликнули Грифон и Якобы Черепаха...

Омаровая Колонна строится по следующему правилу: число омаров в i-м ряду колонны равно i-му числу Фибоначчи, взятому по модулю M.* Для того чтобы проверить правильность построения Омаровой Колонны, Алисе по заданному модулю М и номеру ряда N нужно определить, какое количество омаров должно быть в этом ряду.

* Числа Фибоначчи определяются следующим образом: 1-е и 2-е числа Фибоначчи равны 1. Каждое следующее число Фибоначчи равно сумме двух предыдущих. Несколько первых чисел Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Операция взятия числа A по модулю M – это вычисление остатка от целочисленного деления числа A на M.

Формат входных данных

В первой строке входного файла записано целое число N (1 ≤ N ≤1018+1). Во второй строке записано целое число M (1 ≤ M ≤1000).

Формат выходных данных

В выходной файл необходимо вывести одно число – N-ое число Фибоначчи по модулю M.

Примеры

e. in	e. out
6 4	0
21 1000	946

[*] – при составлении задач были использованы тексты из книги «Приключения Алисы в стране Чудес» в переводе Ю. Нестеренко; http://*****/translations/nesterenko