Задачи Кубка Деда Мороза 25.12.12

В оформлении задач использовались рисунки и цитаты из книги Льюиса Кэрролла

"ПРИКЛЮЧЕНИЯ АЛИСЫ В СТРАНЕ ЧУДЕС. СКВОЗЬ ЗЕРКАЛО И ЧТО ТАМ УВИДЕЛА АЛИСА, ИЛИ АЛИСА В ЗАЗЕРКАЛЬЕ"  

Москва, "Наука" , 1990

Задача А. Белый кролик

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

- Что толку в книжке, - подумала Алиса, - если в ней нет ни картинок, ни разговоров?

Она сидела и размышляла, не встать ли ей и не нарвать ли цветов для венка; мысли ее текли медленно и несвязно - от жары ее клонило в сон. Конечно, сплести венок было бы очень приятно, но стоит ли ради этого подыматься?

Вдруг мимо пробежал белый кролик с красными глазами.

Конечно, ничего удивительного в этом не было. Правда, Кролик на бегу говорил:

- Ах, боже мой, боже мой! Я опаздываю.

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

 Задача

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

Ввод.          Одна строка в формате "чч:мм:cc" (час/минута/секунда).
Вывод.       Количество секунд, оставшееся до полудня.

Пример ввода	Пример вывода
11:59:59	1
12:00:01	86399

 

Задача B. Уменьшение

- Какое странное ощущение! - воскликнула Алиса. - Я, верно, складываюсь, как подзорная труба.

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

- Если я и дальше буду так уменьшаться, - сказала она про себя, - я могу я вовсе исчезнуть. Сгорю как свечка! Интересно, какая я тогда буду?

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

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

Задача

Изначально рост Алисы составлял 120 сантиметров. В первую секунду Алиса уменьшилась на N сантиметров. Во вторую секунду рост Алисы уменьшился на N*K сантиметров. В третью секунду рост ещё уменьшился на N*K*K, а в четвёртую ещё на N*K*K*K. Неужели Алиса исчезнет насовсем? Вычислите рост Алисы, в случае если она так никогда и не найдёт волшебное зелье, которое предотвратит её уменьшение.

Ввод

Два числа N и K в одной строке, разделённые пробелом. (1 <= N <= 100), (0 < K < 1). N - целое число. K - десятичная дробь с двумя знаками после точки. Считайте, что параметры заданы таким образом, что рост Алисы никогда не станет меньше одной сотой сантиметра.

Вывод

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

Пример ввода	Пример вывода
10 0.80	70.00

Задача C. Синяя гусеница

Алиса и Синяя Гусеница долго смотрели друг на друга, не говоря ни слова. Наконец, Гусеница вынула кальян изо рта и медленно, словно в полусне, заговорила:

- Ты... кто... такая? - спросила Синяя Гусеница. Начало не очень-то располагало к беседе.

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

- Что это ты выдумываешь? - строго спросила Гусеница. - Да ты в своем уме?

- Не знаю, - отвечала Алиса. - Должно быть, в чужом. Видите ли...

- Не вижу, - сказала Гусеница.

- Боюсь, что не сумею вам все это объяснить, - учтиво промолвила Алиса. - Я и сама ничего не понимаю. Столько превращений в один день хоть кого собьет с толку.

- Не собьет, - сказала Гусеница.

- Вы с этим, верно, еще не сталкивались, - пояснила Алиса. - Но когда вам придется превращаться в куколку, а потом в бабочку, вам это тоже покажется странным.

- Нисколько! - сказала Гусеница.

- Что ж, возможно, - проговорила Алиса. - Я только знаю, что мне бы это было странно.

- Тебе! - повторила Гусеница с презрением. - А кто ты такая?

Это вернуло их к началу беседы.

Задача

Будем считать что разговор Алисы и гусеницы подчинён простым правилам: набор фраз гусеницы и Алисы ограничен, а также известны все возможные варианты развития разговора. Может ли разговор Алисы и гусеницы длиться бесконечно?

Ввод

Целое число N  - количество правил разговора (0 < N < 100). Далее в N строках следуют две фразы, разделённые пробелом (сами фразы состоят только из букв 'a'..'z' и 'A'..'Z'). Это означает, что если участник разговора скажет первую из этих фраз, то вторая - один из возможных ответов на эту фразу.

Вывод

Выведите 'YES' (без кавычек), если разговор может длится вечно, или 'NO' в противном случае.

Пример ввода	Пример вывода
5 hello Alice Alice caterpillar caterpillar wonderland Alice wonderland wonderland hello	YES

Замечание

В данном примере разговор может длиться бесконечно, например: ...->Alice->wonderland->hello->Alice->...

Задача D. Чеширский кот

Завидев Алису, Чеширский Кот только улыбнулся. Вид у него был добродушный, но когти длинные, а зубов так много, что Алиса сразу поняла, что с ним шутки плохи.

- Котик! Чешик! - робко начала Алиса. Она не знала, понравится ли ему это имя, но он только шире улыбнулся в ответ.

- Ничего, - подумала Алиса, - кажется, доволен. Вслух же она спросила:

- Скажите, пожалуйста, куда мне отсюда идти?

- А куда ты хочешь попасть? - ответил Кот.

- Мне все равно... - сказала Алиса.

- Тогда все равно, куда и идти, - заметил Кот.

- ... только бы попасть куда-нибудь, - пояснила Алиса.

- Куда-нибудь ты обязательно попадешь, - сказал Кот. - Нужно только достаточно долго идти.

Задача

Чтобы как можно быстрее придти куда-нибудь, нужно, конечно же, выбрать дорогу как можно длиннее. А ещё лучше стараться никуда не сворачивать, или, по крайней мере сворачивать только в одну сторону. Представьте что Страна Чудес представляет собой квадратное поле NхN. Алиса располагается в ячейке (x, y) . Алиса может перемещаться по полю по горизонтали и по вертикали. Из начальной позиции Алиса (там, где она встретила Чеширского Кота) может выйти в любом из четырёх направлений. Но дальше она придерживается правил: она либо идёт прямо, либо сворачивает направо. Найдите максимальное число ячеек которое может посетить Алиса, с учётом того, что Алиса не может посещать одну и ту же ячейку дважды.

Ввод

В первой и единственной строке содержатся три целых числа. N   (0 < N < 11), x и y (0 < x, y < N). Нумерация ячеек начинается с единицы.

Вывод

Максимальное число ячеек, которое сможет посетить Алиса, придерживаясь в пути вышеописанных правил.

Пример ввода	Пример вывода
3 2 2	9

Задача E. Безумное чаепитие

Около дома под деревом стоял накрытый стол, а за столом пили чай Мартовский Заяц и Болванщик; между ними крепко спала Мышь-Соня. Болванщик и Заяц облокотились на нее, словно на подушку, и разговаривали через ее голову:

- Бедная Соня, - подумала Алиса. - Как ей, наверно, неудобно! Впрочем, она спит - значит, ей все равно.

Стол был большой, но чаевники сидели с одного края, на уголке. Завидев Алису, они закричали:

- Занято! Занято! Мест нет!

- Места сколько угодно! - возмутилась Алиса и уселась в большое кресло во главе стола.

Задача

Алиса бросила в чашку кусочек сахара, который, естественно, и не подумал таять. В место этого он стал плавать в чае (в состоянии покоя). Найдите объём погружённой в чай части сахара при условиях:

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

2. Сахар представляет собой шар с радиусом k  (0 < k < 1) сантиметров. И массой M  (0 < M < 10) грамм.

3. Выталкивающей силой воздуха пренебречь.

Ввод

В первой и единственной строке содержатся два числа. k и M с точностью два знака после точки.

Вывод

Процент погружённой в чай части сахара от полного объёма кусочка сахара.

Пример ввода	Пример вывода
0.87 2.10	76.13%

Задача F. Грифон

Вскоре они увидели Грифона, крепко спящего на солнцепеке. (Если ты не знаешь, как выглядит Грифон, посмотри на картинку).

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

И она ушла, оставив Алису с Грифоном. Алисе он не внушил особого доверия, но, подумав, что с ним, верно, все же спокойнее, чем с Королевой, она осталась.

Задача

Как же разнообразны грифоны в Стране Чудес. Только представьте, у каждого грифона ровно N перьев, но каждое из них может быть раскрашено в один из K цветов. Грифоны считаются разными, если отличаются цветом хотя бы одного пера (перья у всех грифонов расположены одинаково). Подсчитайте количество различных грифонов.

Ввод

В первой и единственной строке содержатся два целых числа N и K   (0 < N, K < 100).

Вывод

Количество различных видов грифонов 

Пример ввода	Пример вывода
2 2	4

 

Задача G. Суд

- Глашатай, читай обвинение! - сказал Король.

Белый Кролик трижды протрубил в трубу, развернул пергаментный свиток и прочитал:

Дама Червей напекла кренделей

В летний погожий денек.

Валет Червей был всех умней

И семь кренделей уволок

- Обдумайте свое решение! - сказал Король присяжным.

- Нет, нет, - торопливо прервал его Кролик. - Еще рано. Надо, чтобы все было по правилам.

- Вызвать первого свидетеля, - приказал Король. Белый Кролик трижды протрубил в трубу и закричал: - Первый свидетель!

Первым свидетелем оказался Болванщик. Он подошел к трону, держа в одной руке чашку с чаем, а в другой бутерброд.

Задача

Суд в Стране Чудес происходит по следующей схеме. Формируются несколько групп присяжных, каждая из которых решает о виновности или невиновности простым большинством голосов. Чтобы в группе мнения не разделились поровну, все группы состоят из нечётного количества присяжных, а самих групп также нечётное количество. Решения каждой группы записываются на карточки, после чего производится подсчёт количества карточек с "оправданием" и "осуждением". Если карточек "оправдать" больше, то подсудимого отпускают, если нет - казнят на месте. Каково же минимальное количество присяжных, необходимое для вынесения оправдательного приговора?

Ввод

В первой строке - целое нечётное число N - количество групп присяжных (0

Вывод

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

 

Пример ввода	Пример вывода
5 7 5 5 3 9	8

Задача H. Сумма единиц

"Can you do addition?" the White Queen asked. "What's one and one and one and one and one and one and one and one and one and one?" "I don't know," said Alice. "I lost count."

Задача

Сложению тебя обучили? - спросила Белая Королева. - Сколько будет один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один?
      - Я не знаю, - ответила Алиса. - Я сбилась со счета.

Вычислить сумму, названную Белой королевой.

Ввод

 Последовательность из чередующихся слов one и and, разделенных одним пробелом, складывающихся в предложение для счета. Гарантируется правильный порядок слов.

Вывод

Число – сумма единиц.

Пример ввода	Пример вывода
one and one and one and one and one and one and one and one and one and one	10

Задача I. Бег по кругу

Наконец, Додо произнес:

– Победили все! И каждый получит награды!

– А кто же их будет раздавать? – спросили все хором.

– Она, конечно, – ответил Додо, ткнув пальцем в Алису.

Все окружили Алису и наперебой закричали:

– Награды! Награды! Раздавай награды!

Алиса растерялась. В замешательстве она сунула руку в карман – и вытащила оттуда пакетик цукатов.

Задача

В беге по кругу было N участников. В кармане у Алисы был пакетик с M цукатами (2 <= N <= M <=  32000). Алиса хочет разделить цукаты поровну, во всяком случае, так, чтобы количество цукатов у участников отличалось не больше, чем на один. Алиса раздает цукаты по кругу по одному до тех пор, пока у нее не останется цукатов меньше, чем участников бега. Оставшиеся  цукаты она тоже раздает участникам. Сколько кому достанется цукатов?

Ввод

Две строки. В первой целое число N – количество участников. Во второй строке целое число M – количество цукатов.

Вывод

Если цукаты удалось разделить поровну, то вывести количество цукатов, которое получил каждый участник.

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

Пример ввода	Пример вывода
4 12	3
4 14	2 3 2 4

Задачи от A до G были представлены  В. Максименко (xupypr)