Задача A. Этюд в бюджетных тонах ≡

Условие

На следующий день мы встретились в условленный час и поехали смотреть квартиру на Бейкер-стрит, № 221-б, о которой Холмс говорил накануне. В квартире было две удобных спальни и просторная, светлая, уютно обставленная гостиная с двумя большими окнами. Комнаты нам пришлись по вкусу, а плата, поделенная на двоих, оказалась такой небольшой, что мы тут же договорились о найме и немедленно вступили во владение квартирой.

Миссис Хадсон запросила с двух квартирантов помесячно a фунтов стерлингов, b флоринов, с шиллингов, d пенни и e фартингов. Сколько приходится на каждого?

Денежная система Великобритании времен королевы Виктории существенно отличалась от современной десятичной. В частности, тогда...

Один фунт стерлингов был равен 10 флоринам.

Один фунт стерлингов был равен 20 шиллингам.

Один фунт стерлингов был равен 240 пенни.

Один фунт стерлингов был равен 960 фартингам.

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

Единственная строка входного файла содержит пять неотрицательных целых чисел, записанных через пробел: a, b, c, d и e. Гарантируется, что каждое число денежных единиц не может быть увеличено за счет меньших по номиналу. Гарантируется, что эта денежная сумма делится пополам нацело.

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

Выведите через пробел в том же формате пять неотрицательных целых чисел — ответ на вопрос задачи.

Ограничения

0 ≤ a ≤ 100

0 ≤ b ≤ 9

0 ≤ c ≤ 1

0 ≤ d ≤ 11

0 ≤ e ≤ 3

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

10 0 1 0 2

5 0 0 6 1

15 9 1 11 2

7 9 1 11 3

Задача B. Подозрительный регбист ≡

Условие

 — И все-таки, Шерлок, что заставило Вас поставить под сомнение рассказ этого человека? Признаюсь, его внешний вид и повествование о победе в финале олимпийского турнира по регби произвели на меня впечатление!

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

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

1) попытка (5 очков). При занесении попытки команда получает право провести её реализацию и заработать дополнительные очки;

2) реализация (2 очка). Эти очки можно набрать только после удачной попытки;

3) штрафной удар или дроп-гол (3 очка). Эти очки можно набрать в любой момент игры.

Может ли игра в регби действительно завершиться с указанным счетом?

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

Единственная строка входного файла содержит два неотрицательных целых числа, записанных через дефис: a и b — счет игры.

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

Выведите "Yes" или "No" — ответ на вопрос задачи.

Ограничения

0 ≤ a, b ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере приведен невозможный счет 1-0. Если 0 очков команда набрать действительно может (не совершив ни одного результативного действия), то 1 очко в игре набрать нельзя.

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

1-0

No

Задача C. Морской разговор ≡

Условие

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

Мы с Холмсом вышли на вечернюю прогулку и очень скоро оказались в бедняцких кварталах. Страха я не чувствовал, поскольку всегда брал с собой армейский пистолет, а боксерские таланты Шерлока увеличивали мое спокойствие многократно. Внезапно перед нами выросла массивная фигура.

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

 — Стрик лета к шалонику нам пока по пути,  — мгновенно ответил мой спутник,  — а вы, я вижу, опытный морской волк, успели побывать и в Японии, и в Патагонии, не говоря уже о Вест-Индии! Обидно, что Вас списали на берег из-за травмы ноги.

Уже вернувшись домой и наслаждаясь теплом от камина, мы неторопливо беседовали. Шерлок Холмс объяснил мне систему обозначений морских направлений (румбов). Есть четыре основных румба: Север (N), Восток (E), Юг (S) и Запад (W), а также четыре производных: Северо-запад (NW), Северо-восток (NE), Юго-восток (SE) и Юго-запад (SW). Обозначения румбов, отстоящих от основных на 11,25 градусов, получаются из обозначений одного из восьми выше перечисленных румбов, с добавлением после них слова «тень» (b) и названия основного направления, к которому отклоняется румб. Обозначения румбов, отстоящих от основных на 22,5 градусов, получаются из обозначений производных от основных румбов, с добавлением перед ними названия основного направления, к которому отклоняется румб. Специально для меня даже нарисовали розу румбов,  — увы, весь мой армейский опыт был исключительно сухопутным, поэтому все сказанное оказалось для меня в новинку.

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

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

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

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

Ограничения

Гарантируется корректность входных данных.

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

Смотри рисунок.

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

N

S

NbE

SbW

Задача D. Учат в интернате ≡

Условие

После блистательного раскрытия дела о пропавшем мальчике, нам с Холмсом устроили экскурсию по интернату. Между делом, мистер Хакстейбл рассказал о начале одного смелого педагогического эксперимента — совместном обучении мальчиков и девочек. Пока был сформирован только один класс, где было поровну детей каждого пола.

Прежде всего следует сказать, что ребят (и девочек, и мальчиков) в интернате относили к одной из двух категорий, считая их либо успевающими, либо неуспевающими. Всего в классе было n учащихся, из них b успевающих мальчиков (соответственно, n2 − b неуспевающих) и g успевающих девочек (соответственно, n2 − g неуспевающих). В результате анализа педагогической деятельности в этой области других учебных заведений, стало известно следующее:

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

Под общей успеваемостью будем понимать количество успевающих обучающихся.

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

Три строки входного файла содержит три неотрицательных целых числа: n, b и g. Гарантируется четность n.

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

Выведите "Yes" или "No" (без кавычек) — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 100

0 ≤ b, g ≤ n2

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере дан класс, в котором 2 ученика (1 мальчик и 1 девочка). Мальчик успевающий, девочка — нет. Посадить за парты их можно единственным образом, после чего их успеваемость не изменится: мальчик останется успевающим, девочка останется неуспевающей. Общая успеваемость была равна 1 и не стала выше (тоже 1). Ответ — нет.

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

2
1
0

No

Задача E. Установление адреса ≡

Условие

 — Знаете, Холмс, мне всё не дает покоя тот обрывок бумажки с таинственным шифром, найденный Лестрейдом неподалёку от вчерашнего места преступления. Он не стал показывать его Вам, а сразу приобщил к вещественным доказательствам и отправил в Скотланд-Ярд. Но мне удалось украдкой на него взглянуть, и я запомнил каждый символ!

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

 — Он совсем короткий, в нем всего три слова. Первое — NW1, второе — 6XE, третье ...

 — Неужели 1F?

 — Холмс, но как Вы догадались?

 — Это очень просто, мой дорогой друг! Никакой это не шифр, это почтовый код, причем нашего с Вами дома. С тех самых пор, как здесь открыли музей Шерлока Холмса, количество корреспонденции, которое нам доставляет бедняга почтальон, возросло в разы. Видимо это обрывок вчерашнего ненужного письма, которое миссис Хадсон выкинула в мусорный ящик, а северо-западный ветер как раз дул в направлении места преступления.

После этого мой друг прочитал мне небольшую лекцию о современной системе почтовой адресации. Из неё я узнал, что индексы британской Королевской почты существенно отличаются от принятых в большинстве стран числовых почтовых индексов. Они состоят из двух частей, разделенных пробелом. А каждому получателю дополнительно присвоен двухсимвольный код DPS (delivery point suffix) — вместе с индексом он однозначно определяет почтовый ящик, в который осуществляется доставка почты. Например, наш с Холмсом дом получил почтовый ящик с адресом NW1 6XE 1F. Здесь NW соответствует северо-западному Лондону, а в нем округ с номером 1 — части Вестминстера и части Камдена. 6XE определяет участок улицы Бейкер-стрит, а уже 1F — конкретный почтовый ящик для доставки корреспонденции.

Существует всего 6 шаблонов для первой части индекса (до пробела): A9, A99, AA9, A9A, AA9A и AA99. Здесь символ "A" означает любую заглавную латинскую букву, а символ "9" — любую цифру от 1 до 9. Вторая часть индекса имеет единственный формат 9AA, а DPS — тоже единственный формат 9A.

Используя эту информацию из дневника доктора Ватсона, определите по данной строке, соответствует ли она шаблону Британского почтового адреса.

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

Единственная строка входного файла содержит строку s — символы с ASCII кодами от 32 до 126.

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

Выведите одно слово "YES" или "NO" (без кавычек) — ответ на задачу.

Ограничения

1 ≤ len(s) ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснения к примерам

В первом примере приведен реальный адрес дома №221-В Бейкер-стрит. Во втором примере использована недопустимая цифра 0.

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

NW1 6XE 1F

YES

ZP07 7CF 6V

NO

Задача F. Трава у дома Месгрейвов ≡

Условие

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

 — Что же его останавливало, дорогой Холмс? Неужели древняя корона английских королей не стоит какого-то газона?

 — Это был не просто газон, а настоящее произведение искусства! Месгрейвы несколько столетий возделывали его и в результате получился просто идеальный ландшафт. "Укажите мне место, где может быть зарыт клад, — сказал Реджинальд, — и я разрешу раскопки именно в этом месте. Но копать там, где клада точно быть не может, я не позволю!"

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

 — Нет ничего зазорного в том, чтобы обратиться к помощи профессионала. Я нанес визит сэру Чарльзу Бэббиджу, описал стоящую перед нами задачу и попросил определить координаты тех участков газона, где может быть спрятано сокровище. Ученый заинтересовался, настроил свою аналитическую машину и загрузил в неё стопку картонок. Я уже приготовился к томительному ожиданию, сопровождаемому обычными стенаниями Бэббиджа о том, как ему докучают уличные музыканты, как вдруг он с улыбкой поворачивается и протягивает мне готовые перфокарты. На верхней было выбито точное количество возможных мест, а на остальных — их координаты. Нам с Месгрейвом повезло, уже пятая по счету раскопка привела к успеху.

Заметка на полях дневника Джона Ватсона: "Боюсь, что рассказ Холмса выглядит несколько ... фантастически. Требуется проверка со стороны какого-нибудь молодого исследователя, возможно ли с помощью вычислительного устройства и половины инструкции быстро определить все места, где спрятано сокровище?"

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: m и n — размер участка, на котором зарыт клад. Вторая строка содержит натуральное число k — количество чисел в инструкции. В третьей строке через пробел расположены k натуральных чисел p_i — количество шагов до очередного поворота.

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

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

Ограничения

1 ≤ m, n ≤ 60

1 ≤ k, p_i ≤ 30

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере дан участок размером 10 на 6, место старта всегда в участке с координатами (1, 1). В инструкции три команды: пройти 5 шагов, повернуть налево или направо (часть инструкции с точными направлениями поворотов утрачена) пройти ещё 2 шага, повернуть налево или направо, пройти 4 шага и копать. С учетом того, что ни на каком шаге нельзя выходить за пределы участка, есть всего три подходящих места, где может быть зарыто сокровище.

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

10 6
3
5 2 4

3
2 3
3 2
10 3

Задача G. Хештег рыжих ≡

Условие

Союзу рыжих нужен новый представитель! Объявление об этом событии опубликовано на первой полосе газеты "Times". Каждый соискатель отправляет по электронной почте своё резюме с фотографией и ждёт результата.

Всего фирма получила n писем-заявок. Для более тщательного отбора решено пригласить на собеседование не менее k человек. Естественно, они должны быть как можно более рыжими.

Цвет волос каждого кандидата определяется по фотографии в формате цвета HTML в виде символа "хештег" и трёх пар шестнадцатеричных цифр, где каждая пара отвечает за свой цвет: две первые цифры — красный, две в середине — зелёный и две последние цифры — синий. Например, абсолютный блондин будет записан как #FFFFFF, брюнет — как #000000, серый цвет волос будет закодирован как #808080 и так далее. Чистый рыжий цвет, взятый за образец, имеет формат #D77D31.

Для определения того, насколько близок цвет волос кандидата к образцу, используется Манхэттенское расстояние — сумма модулей разностей соответствующих значений. Например, для блондина этот параметр окажется равен |D7₁₆ − FF₁₆| + |7D₁₆ − FF₁₆| + |31₁₆ − FF₁₆| = 40 + 130 + 206 = 376, для брюнета |D7₁₆ − 00₁₆| + |7D₁₆ − 00₁₆| + |31₁₆ − 00₁₆| = 215 + 125 + 49 = 389, для сероволосого — 169, для почти рыжего #D57A39 — 13, для образцово рыжего — нулю.

Помогите Союзу рыжих определить наименьшее значение параметра, достаточное для приглашения на собеседование не менее k кандидатов из n с наиболее близким к образцу цветом волос.

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

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

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

Выведите одно неотрицательное целое число — минимальное значение параметра, которому будут соответствовать не менее k кандидатов из n.

Ограничения

1 ≤ k ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере имеется шесть кандидатов, из которых нужно выбрать трёх "наиболее рыжих". Этот параметр для первого кандидата будет равен 376, для второго — 389, третьего — 169, четвертого — 307, пятого — 297, шестого — 274. Таким образом, значения 297 достаточно для приглашения на собеседование трёх соискателей (третьего, пятого и шестого).

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

6 3
#FFFFFF
#000000
#808080
#123456
#9ABCDE
#DDDDDD

297

Задача H. Дьяволова игра ≡

Условие

"Обратите внимание, дорогой доктор, погибшие играли в Баккару". Холмс внимательно осмотрел разбросанные по столу карты. "Судя по записям, ставки выросли до значительных сумм. Кто-то четвёртый был здесь, крупно проигрался, ушел, потом вернулся и каким-то образом умертвил своих партнеров по игре".

Я промолчал. Помочь моему другу больше было нечем, поскольку все свои соображения, связанные с медицинскими аспектами дела я уже высказал. Никогда не понимал этой человеческой слабости к азартным играм. "Возрадуется диавол и налетит, увидев свой час: бесчинствуют грешники игрою в кости и в карты, и всякими иными играми бесовскими тешатся", — сказано в Писании. Не отнесу себя к пуританам, но в отношении игр на деньги они абсолютно правы. Хорошо еще, что эта слабость обошла стороной Шерлока. Мне хватало и его пристрастия к опиуму.

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

Заметки на полях дневника доктора Ватсона: "Описать правила игры. Возможно пригодится для нового рассказа".

Цель игры в Баккару — набрать комбинацию карт с общим числом очков 9 или как можно более близким к 9. Туз засчитывается за одно очко, карты с 2 по 9 — по номиналу, фигуры и десятки дают ноль очков. Сначала игрок получает две карты. Если общая сумма равна 10 или более, из неё вычитается 10, а остаток учитывается при подсчетах результатов. Например, 7 + 6 = 13 = 3 или 4 + 6 = 10 = 0. Правило третьей карты определяет, когда игроку автоматически выдается еще одна карта. Если игрок первыми двумя картами набрал от 0 до 5 очков, то он получает третью карту, если набрано больше 5 очков, то не получает.

В игре используется стандартная колода из 52 карт. Игрок получил первую карту номиналом n из новой колоды. Определите вероятность того, что он наберет ровно 9 очков (возможно, получив и третью карту из оставшейся части колоды).

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

Единственная строка входного файла содержит целое неотрицательное число n.

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

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

Ограничения

0 ≤ n ≤ 9

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере игрок получил карту номиналом 0 (это может быть десятка или картинка — валет, дама или король). Игрок наберет 9 очков, если сразу получит девятку или пару карт с номиналами 0 + 9, 1 + 8, 2 + 7, 3 + 6, 4 + 5 или 5 + 4.

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

0

2 15

Задача I. Вандал в Суссексе ≡

Условие

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

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

 — Еще одна...

 — Еще одна?

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

 — Что же Вы не проверите все оставшиеся книги?

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

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

 — Есть!  — воскликнул он примерно через 15 минут.  — Закономерность есть!

В библиотечной книге было ровно n листов, по одной странице с каждой из двух сторон (на k-м по счету листе располагались страницы с номерами 2 × k − 1 и 2 × k). При очередной проверке оказалось, что из книги вырезан лист, сумма цифр номеров страниц на котором максимальна. По известному n определите эту сумму.

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

Единственная строка входного файла содержит натуральное число n — первоначальное количество листов в книге.

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

Выведите одно натуральное число — ответ на задачу.

Ограничения

1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.

Пояснение к примеру

В примере книга первоначально состояла из 10 листов (20 страниц). Вырван был предпоследний лист, сумма цифр двух номеров страниц на нем равна 1 + 7 + 1 + 8 = 17 — больше, чем на всех остальных.

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

10

17

Задача J. Перевернутое пятно ≡

Условие

Видя изумление прославленного специалиста, Лестрейд захихикал от восторга.

— Ну, а теперь я объясню вам, в чем дело. Второе пятно тоже существует, но оно не совпадает с первым. Взгляните сами.

С этими словами он приподнял другой конец ковра, и действительно, на светлых квадратах паркета, ближе к старинной двери, мы увидели большое темно-красное пятно.

— Что вы скажете об этом, мистер Холмс?

— Здесь все очень просто. Два пятна совпадают друг с другом, но ковер был перевернут. Так как он квадратный и не прикреплен к полу, это было легко сделать.

Помогите доктору Ватсону нарисовать в блокноте изображение перевернутого ковра.

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

Первая строка входного файла содержит натуральное число n — размер стороны ковра. В следующих n строках расположено описание ковра — n символов "." (ASCII-код 46, чистое место) или "#" (ASCII-код 35, испачканное место). В последней строке расположено направление поворота — одно из трех английских слов: "Right" (означает, что ковер требуется повернуть на 90^∘ по часовой стрелке), "Left" (означает, что ковер требуется повернуть на 90^∘ против часовой стрелки), "U-turn" (означает, что ковер требуется повернуть на 180^∘).

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

Выведите n строк по n символов в каждой — описание ковра после поворота.

Ограничения

1 ≤ n ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

3
..#
.##
...
Right

...
.#.
.##

3
..#
.##
...
U-turn

...
##.
#..

Задача K. Пять наследников мандарина ≡

Условие

Молодой человек придвинул кресло и протянул мокрые ноги к пылающему камину.

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

В результате непродолжительного рассказа выяснилось следующее: после трагической смерти китайского чиновника осталось пятеро наследников. Стоимости всех n вещей, подлежащих дележу, выражаются числами от 1 до n без повторений. Традиции требуют, чтобы сумма всех ценностей, доставшихся каждому наследнику была равной. Удастся ли нам это сделать?

 — Вы обратились не вполне по адресу, — ответил Шерлок Холмс.  — Но заданный вами вопрос настолько прост, что я легко на него отвечу...

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

Первая строка входного файла содержит длину n, вторая — само число n.

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

Выведите "Yes" или "No" — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

Первый наследник получит одну вещь стоимостью 9, второй — две вещи стоимостью 8 и 1, третий — 7 и 2, четвертый — 6 и 3, последний — 5 и 4. Все предметы распределены, все доли наследства равны.

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

1
9

Yes

Задача L. Месть Наполеонов ≡

Условие

Анализируя карту с местами уже совершенных дерзких ограблений, целью которых были бюсты Императора, молодой сыщик Шерлок Холмс обнаружил интересную особенность — все они располагались на одной окружности исключительно в точках с целочисленными координатами. Поскольку на этой окружности осталась всего одна не отмеченная точка, может быть, нужно определить её координаты и устроить засаду?

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

Первая строка входного файла содержит одно натуральное число n. В следующих n строках через пробел расположены два целых числа x_i, y_i — координаты очередного ограбления. Гарантируется, что все (кроме одной) точки с целочисленными координатами, лежащие на этой окружности, перечислены во входных данных. Также гарантируется, что центр окружности лежит в точке пересечения прямых y = x + z₁ и y =  − x + z₂, где z₁ и z₂  — некоторые целые числа.

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

Выведите через пробел два целых числа — координаты места засады.

Ограничения

1 ≤ n ≤ 100

 − 100 ≤ x_i, y_i ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие, когда центр окружности совпадает с началом координат, получат не менее 60 баллов.

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

3
0 0
0 1
1 0

1 1

7
3 4
3 0
0 1
1 4
1 0
4 3
4 1

0 3

Задача M. Собака Мортимера ≡

Условие

— A собака?

— Имела обыкновение носить за своим господином эту трость. Собака крепко держала палку, поэтому остались следы ее зубов. Пространство, занимаемое этими следами, показывает что челюсть собаки велика для терьера и мала для мастифа.

По координатам отметин зубов на палке определите размер челюсти собаки.

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

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

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

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

Ограничения

2 ≤ n ≤ 100

 − 10000 ≤ x_i ≤ 10000

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 3, получат не менее 10 баллов.

Решения, верно работающие при n = 4, получат не менее 20 баллов.

Пояснение к примерам

В первом примере существует единственный подходящий размер пасти пса — 1. Собака брала зубами палку двумя способами: в точках с координатами 1 и 2 и в точках с координатами 2 и 3.

Во втором примере минимальный возможный размер пасти тоже равен 1. Собака брала зубами палку в точках с координатами 1 и 2 и в точках с координатами 11 и 12. Максимальный возможный размер пасти равен 10. Собака брала зубами палку в точках с координатами 1 и 11 и в точках с координатами 2 и 12. Максимальный размер не может быть равен 11, в этом случае собака не смогла бы сделать отметки в точках 2 и 11.

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

3
1 2 3

1 1

4
1 2 11 12

1 10

Задача N. Поющие человечки ≡

Условие

Когда я просыпаюсь среди ночи от тоскливых однотонных звуков скрипки Шерлока Холмса, мне всегда вспоминается его блистательное решение проблемы, с которой к нам обратился Ханс Рихтер, дирижер только что созданного Лондонского симфонического оркестра.

 — Мне рекомендовали Вас, мистер Холмс, как человека равно одаренного как в области музыки, так и в раскрытии преступлений. Дело, с которым я вынужден к Вам обратиться, это, конечно, не убийство и не ограбление на крупную сумму... но мошенничество самого грязного сорта! Как Вам известно, я собрал музыкантов и хористов из самых разных стран. У меня абсолютный слух, и даже лучше — я могу определить уникальность каждого музыканта по собственной шкале. Мне удалось собрать в один хоровой коллектив n исполнителей с разными степенями уникальности от 1 до n. Но когда хор впервые собрался вместе и исполнил "Правь, Британия!" — я был шокирован! Уникальность хора не равнялась сумме чисел от 1 до n, как должно было быть! В хор затесался какой-то мошенник, пройдоха, неумеха с нулевой уникальностью!

 — Что же мешает Вам прослушать отдельно каждого?

 — Все эти люди (ну, кроме этого одного) — необычайно одаренные, талантливые, и, как следствие, необыкновенно обидчивые! Попытка устроить индивидуальное прослушивание может быть воспринята ими как оскорбление, как сомнение в их несомненном таланте! Нет, мистер Холмс, найдите другое решение, умоляю Вас!

 — А чему равнялась уникальность хора? по вашей шкале?

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

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

Единственная строка входного файла содержит неотрицательное целое число s — сумму уникальностей хористов.

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

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

Ограничения

0 ≤ s ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере дано s = 4. Такое возможно, если из трех исполнителей с уникальностями 1, 2 и 3 заменить второго артиста самозванцем с нулевой уникальностью: 1 + 0 + 3 = 4.

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

4

2

Задача O. Человек с рассеченной судьбой ≡

Условие

Мистеру Невиллу Сент-Клеру 37 лет. Живет он скромно, хороший муж и любящий отец, люди, встречающиеся с ним, отзываются о нем превосходно. Определенных занятий у него нет, но он принимает участие в нескольких коммерческих предприятиях. Обосновался на собственной вилле "Кедры" в Кенте.

Угрюмый калека Хью Бун — профессиональный нищий, для вида продающий восковые спички. У него оранжево-рыжие волосы, бледное лицо, изуродованное чудовищным шрамом, и отменное чувство юмора, выделяющее его из толпы попрошаек. Дождь милостыни так и льется в грязную кожаную кепку, которая лежит перед ним на мостовой, в нише на левой стороне лондонской Трэд-Нидл-стрит.

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

Помогите мистеру Невиллу определить количество подходящих расписаний на ближайшие n дней, из которых ровно k дней он посвятит "работе". Чтобы не вызвать подозрений у полиции, Хью Бун никогда не просит милостыню два дня подряд. Также известны дни, когда Сент-Клер должен будет остаться дома.

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

Первая строка входного файла содержит натуральное число n — общее количество дней. Вторая строка содержит натуральное число k — количество дней, в течение которых Невилл собирался просить милостыню. Третья строка входного файла содержит натуральное число p — количество дней, которые ему нужно провести с семьей. В четвертой строке через пробел в порядке возрастания расположены натуральные числа d_i — номера таких дней.

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

Выведите одно неотрицательное целое число — количество подходящих расписаний.

Ограничения

1 ≤ n ≤ 100

1 ≤ k, p, d_i ≤ n

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере из пяти дней Невилл два дня хочет посвятить сбору милостыни. К сожалению (или к счастью?) в первый, второй и пятый день он должен быть с семьей, а "работать" два дня подряд (в третий и четвертый) он не может. Подходящих расписаний нет.

Во втором примере Невилл сможет "работать" два дня из пяти (в третий и пятый дни). Расписание единственное.

В третьем примере Невилл должен быть с семьей только в четвертый день. Есть четыре подходящих расписания:

Невилл "работает" в первый и третий дни;

Невилл "работает" в первый и пятый дни;

Невилл "работает" во второй и пятый дни;

Невилл "работает" в третий и пятый дни.

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

5
2
3
1 2 5

0

5
2
3
1 2 4

1

5
2
1
4

4

Задача P. Признак четырех ≡

Условие

 — Итак, господа, в соответствии с завещанием, для подтверждения прав на сокровища Агры четверо претендентов должны назвать кодовое число. Насколько я понимаю, у каждого из вас есть какая-то информация об этом числе, его признак. Я могу дать Вам время посовещаться, но предупреждаю, что у Вас будет единственная попытка. В случае, если Ваше число не совпадёт с моим, сокровище поступает в полное распоряжение Короны.

Такими словами завершил свое торжественное заявление глава адвокатской конторы "Lloyds and Sons". Мы переглянулись. Пришло время открыть карты. Каждый понимал, чем чревата ошибка.

 — Мне известно, что при делении этого числа на a получится остаток x,  — первой нарушила молчание Мэри Морстен.

 — Мы знаем, что при делении этого числа на b получится остаток y, а при делении на c получится остаток z  — отозвался один из братьев Шолто. Признаюсь, я до сих пор путал, кто из них кто.

 — Подходящих чисел всё ещё бесконечно много. Ну же, Джонатан Смолл, ваш черед. Или сокровище получают все, или никто, назад пути нет,  — в голосе Холмса послышались стальные нотки.

 — Ладно, ваша взяла. Из всех подходящих натуральных чисел нужно взять n-е по счету,  — разомкнул уста бывший каторжник.

 — Итак, господа, Вы готовы?  — спросил мистер Ллойд.

Мы растеряно молчали. В конце концов все взоры устремились на Холмса. Сможет ли он и на этот раз блеснуть своим интеллектом?

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

Первая строка входного файла содержит натуральное число a и неотрицательное целое число x. Во второй и третьей строках в том же формате записаны числа b и y, а также c и z. В четвертой строке расположено натуральное число n. Гарантируется простота чисел a, b и c.

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

Выведите одно натуральное число — ответ на задачу.

Ограничения

2 ≤ a, b, c ≤ 97

0 ≤ x ≤ a − 1

0 ≤ y ≤ b − 1

0 ≤ z ≤ c − 1

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 1, получат не менее 20 баллов.

Решения, верно работающие при x = y = z = 0, получат не менее 20 баллов.

Пояснение к примеру

В примере нужно найти второе по счету число, которое имеет остаток остаток 1 при делении на два (то есть оно нечетное), имеет остаток 2 при делении на три и нацело делится на пять. Первое из таких натуральных чисел — 5, второе — 35.

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

2 1
3 2
5 0
2

35

Задача Q. Клейкая лента ≡

Условие

После женитьбы я стал редко видеть Шерлока Холмса. Мы с супругой поселились в Паддингтоне, где я купил врачебную практику, к сожалению, не приносящую стабильного дохода. Дни шли спокойно и чинно, пламя любви озаряло их таинственным светом.

Однажды в нашу дверь постучали. Решив, что кому-то из соседей потребовалась медицинская помощь, я поспешил вниз. Однако посетитель был мне незнаком. Учтиво приподняв котелок и уточнив, что перед ним стоит именно доктор Джон Ватсон, молодой человек попросил уделить ему несколько минут наедине. На меня нахлынула волна ностальгии, Бог его знает, сколько раз к нам с Холмсом приходили чужие люди с самыми разными просьбами... Интересно, смогу ли я, как мой друг, определить род занятий своего визитера?

Одет небогато, но опрятно, гладко выбрит и аккуратно подстрижен. Речь выдает иностранца, скорее немца. В руке небольшой докторский саквояж, но нет, назвать его доктором я бы не осмелился. После стольких лет практики своих коллег начинаешь узнавать издалека, сразу и без ошибок. Да и на пациента не похож, не выглядит ни больным, ни встревоженным. Что еще? Приехал издалека, из кармана торчит железнодорожный билет, видимо сегодня же уедет обратно. Ко мне с визитом пришел не к первому, лондонский поезд (а откуда еще мог приехать посетитель) прибыл ранним утром. Да и крошки на усах — уже успел у кого-то позавтракать. Умеет расположить к себе, учтив и воспитан.

 —Вижу, Вы гадаете, кто же я такой?  — улыбнулся молодой человек, открыв саквояж, откуда мгновенно появились бумажные упаковки.  —Не буду скрывать, я — коммивояжер, представляю фирму "Beiersdorf". Мы хотим познакомить Вас с интересным изобретением, клейкой лентой с лекарственным антибактериальным покрытием. Ваши коллеги прозвали его лейкопластырем. С его помощью можно зафиксировать края небольшой раны, чтобы избежать заражения крови, также им можно ...

 —Джеймс, скорее!  — в комнату ворвалась жена. Понятия не имею, почему с глазу на глаз она зовет меня другим именем.  —Кэйт чистила рыбу и сильно поранила руку, глубокий порез около 10 дюймов. Сделай что нибудь! Ой, простите, я не знала, что у тебя посетитель...

 —Вот и случай проверить в деле наш чудо-пластырь!  — воскликнул тот.  — У меня с собой два вида упаковки: в одной ленты длиной a дюймов и стоимостью x шиллингов каждая, во второй ленты длиной b дюймов и стоимостью y шиллингов за штуку. Если результат Вас удовлетворит, наша фирма готова высылать по почте любое необходимое количество этой лекарственной формы. Постоянным клиентам скидка!

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

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и x — длину и стоимость лейкопластыря первого типа. Вторая строка входного файла содержит два натуральных числа, записанных через пробел: b и y — длину и стоимость лейкопластыря второго типа. В третьей строке содержится одно натуральное число c — длина пореза.

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

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

Ограничения

1 ≤ a, b, x, y ≤ 100

1 ≤ c ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при a = b, получат не менее 20 баллов.

Пояснение к примеру

В примере дано два типа лейкопластырей: первый длиной 3 дюйма и стоимостью 2 шиллинга за штуку, второй длиной 4 дюйма и стоимостью 3 шиллинга за штуку. Порез у Кэйт имеет длину 10 дюймов.

Доктору выгоднее потратить два лейкопластыря первого типа и один — второго. Суммарная длина составит 3 + 3 + 4 = 10 дюймов (достаточно для оказания первой помощи), а стоимость — всего 2 + 2 + 3 = 7 шиллингов.

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

3 2
4 3
10

7

Задача R. Болельщик на покое ≡

Условие

 — Опять собрались на Уэмбли, доктор? Тыкать болельщикам в лоб бесконтактным термометром?

 — Опять, Холмс! Совмещу приятное с полезным. Поучаствую во входном контроле, а потом нас проводят в специальную ложу и дадут досмотреть матч с хорватами. Будете смотреть трансляцию? Нас обещали показать в перерыве.

 — Нет уж, увольте... Эти страсти мне неведомы и непонятны. Лучше возвращайтесь с известием о каком-нибудь таинственном происшествии, а то мой мозг скоро заржавеет от бездействия на карантине.

 —Счастливо оставаться!

 —Маску не забудьте.

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

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

Футбольный турнир среди нескольких (не менее двух) команд проходил в один круг (каждая команда сыграла с другой командой ровно один раз). За победу в футбольном матче дают 3 очка, за ничью — одно, за поражение — ноль. По окончании турнира оказалось, что все команды набрали в сумме ровно n очков. Сколько команд участвовало в этом турнире?

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

Единственная строка входного файла содержит натуральное число n.

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

Выведите через пробел два натуральных числа — наименьшее и наибольшее возможное количество команд в турнире. Выведите число -1, если такое количество очков набрать невозможно.

Ограничения

1 ≤ n ≤ 10¹⁶

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 1 ≤ n ≤ 1000, получат не менее 60 баллов.

Пояснение к примерам

В первом примере невозможно набрать 1 очко — в одной игре разыгрывается 2 или 3 очка.

Во втором примере 8 очков можно набрать только в случае участия в турнире трёх команд. Одна из команд одержит две победы и наберет 6 очков, две другие сыграют между собой вничью и наберут по одному очку.

В третьем примере набрать 30 очков можно двумя способами:

1) в турнире для 5 команд ни один матч не завершился вничью;

2) в турнире для 6 команд все матчи завершились вничью.

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

1

-1

8

3 3

30

5 6

Задача S. Исчезновение дочери леди Фрэнсис Карфэкс ≡

Условие

 — Мистер Холмс, моя дочь Алиса пропала. Полиция (леди Карфэкс метнула гневный взгляд в сторону Грегсона) ничего не может сделать. Мое сердце подсказывает мне, что ее удерживают насильно и пытаются добраться до денег. Я прошу Вас разыскать ее.

 — Расскажите про девушку,  — промолвил Холмс, набивая трубку.

 — Алиса богата, даже весьма состоятельна. Мой покойный брат оставил ей огромное наследство. Она и раньше была непокорным ребенком, а как получила состояние, стала просто несносной. Постоянно спорила со мной, доходило до скандалов. Это всё суфражистки сбили ее с толку, эти гарпии знают, где можно поживиться. Полгода назад Алиса заявила мне, что хочет съехать из родного дома и путешествовать по стране. "Налегке, инкогнито, хочу вдохнуть воздух свободы",  — говорила она. С тех пор я ее не видела. Единственная связь между нами  — письма, которые она время от времени отправляет из самых разных мест.

 — Вот, письма!  — не удержался Грегсон.  — Последнее письмо пришло три дня назад. Почему полиция должна ее искать, если с ней всё в порядке? Да сами прочитайте.

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

Приветствую!

Очередной месяц — очередной город. Исследую Телфорд. Ежедневно моюсь, ем нормально.

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

Опаздываю, убегаю!

До свидания! Только отличных дней!

Ваша Алиса.

 — Это ее почерк,  — продолжал инспектор. Я считаю, что никаких поводов для беспокойства нет. Из уважения к Вам, леди Карфэкс, мы негласно прочесали и город Телфорд, и весь Шропшир.  — Следов девушки не нашли, но, скорее всего, она уже уехала в другое место.

Внезапно у меня перехватило дыхание. Я увидел...

 — Господи, Грегсон, даже Ватсон уже сообразил в чем дело!  — не выдержал Холмс.

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

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

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

Выведите для каждого числа x_i ответ — "Yes" или "No" (без кавычек) — равно ли это число номеру дома, в котором удерживается девушка.

Ограничения

1 ≤ n ≤ 100

1 ≤ x_i ≤ 1000

Система оценки и описание подзадач

Баллы за задачу начисляются только в случае, если все тесты успешно пройдены.

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

5
1
777
68
13
6

No
No
No
No
No

Задача T. Посеребрённый ≡

Условие

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

 — Вот этот?  — лениво отозвался ростовщик, вытаскивая украшение из витрины.  — Хм, проба невысокая, можно даже сказать, что не серебряный, а посеребрённый. Лежит недавно. Надо поднять приходные книги, но вы же понимаете, господин полицейский, человек назовётся мистером Смитом, а кто он на самом деле — Бог знает. Ну вот, так и есть — мистер Смит.

Мы вышли из ломбарда, попрощались с Грегсоном и направились домой. Но пройдя всего пару шагов, Холмс остановил меня и предложил вернуться назад.

 — Давайте поговорим без полиции. По вашему лицу я понял, что у Вас с ней напряженные отношения. Но я просто частный детектив. Этот кулон — наша единственная зацепка. Его хозяйка похищена. Ей удалось сообщить своей семье адрес, где её держали, но мы опоздали. Главарь накануне перевез её в неизвестное место. Держу пари, Вам есть, что рассказать нам о человеке, сдавшем этот кулон пару дней назад, помимо его вымышленного имени. Кроме того, (тут Холмс многозначительно повертел в руке золотую гинею) сведения будут оплачены.

 — Похищение, говорите... Да, было видно, что этот человек способен на всё. Ладно, расскажу Вам всё, что знаю, и о чем предполагаю. А деньги уберите, не возьму я их. У самого дочки подрастают. Хотя... давайте услуга за услугу. Я тут недавно работаю, а так как в вычислениях никогда силен не был, часто ошибаюсь при переводе пробы драгоценного металла из каратной в старую английскую и наоборот. Вот если бы Вы мне объяснили как это делается...

Основой каратной системы проб является количество карат основного благородного металла (в нашем случае серебра) в 24 каратах сплава. Так, при пробе 9 карат, масса серебра в сплаве составляет 0,375 от веса сплава, а при пробе 12 карат — 0,5, то есть половина сплава состоит из чистого серебра, а половина из других металлов. При пробе 24 карата мы имеем серебро в чистом виде.

До принятия метрической системы проб для серебра в Англии также использовали тройскую систему: указывали число тройских унций и пеннивейтов (120 унции) в 12 тройских унциях серебра. Например, при пробе 6 унций 0 пеннивейтов масса серебра составляет 0,5 сплава, то есть ровно половину, а при пробе 11 унций и 15 пеннивейтов — 0,9791(6) от массы сплава, то есть почти чистое серебро.

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

Первая строка входного файла содержит натуральное число n, выражающее из каких единиц в какие следует переводить. При n = 1 во второй строке записано целое неотрицательное число x — проба ювелирного изделия в каратах. Необходимо перевести это количество в тройские унции и пеннивейты.

При n = 2 во второй строке через пробел записаны два целых неотрицательных числа a и b — проба ювелирного изделия в тройских унциях и пеннивейтах. Необходимо перевести это количество в караты. Гарантируется корректность входных данных.

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

Выведите значение пробы серебра в сплаве в нужной пробе. Если ответ получился натуральным — выведите только целую часть. В противном случае отделите целую часть от дробной символом "." (ASCII код 46). Не выводите незначащих нулей. В случае перевода в старую английскую систему, если количество пеннивейтов равно нулю, выводить их не нужно.

Ограничения

1 ≤ n ≤ 2

0 ≤ x ≤ 24

0 ≤ a ≤ 12

0 ≤ b ≤ 19

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

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

1
21

10 10

2
11 15

23.5

Задача U. Медные буки и бяки ≡

Условие

 — Отвлеките хозяина, а я пока поищу мисс Алису. Негодяй держит её взаперти где-то в доме,  — прошептал Холмс мне на ухо.

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

 — Так Вы бывали в Индии?  — с самым невинным видом продолжил я разговор, и (видит Бог, удача была сегодня на моей стороне) по тому, как загорелись глаза нашего противника, понял, что попал в яблочко.

 — Бывал? Да я там служил во время подавления восстания сипаев! Посмотрите, сам Великий Могол подарил мне эту безделушку!  — и мы проследовали к дальней стене, где на столике были расставлены какие-то небольшие фигурки двух видов.  — Это символы индийских духов неудач и печалей, что-то вроде наших бук и бяк. Индусы раскладывают их по двум кучкам, буки в одну, бяки в другую, а потом играют, убирая и добавляя фигурки.

 — Что Вы говорите? Как интересно!  — я как мог тянул время. Врет он, подумалось мне, наверняка стащил эту диковинку во время разграбления дворца раджи. Впрочем, время тогда было иное, как-никак тридцать лет прошло. Сейчас на многие вещи смотришь по-другому.

 — Они были сделаны из качественной меди местными мастерами. Хотите научу Вас играть? Это очень просто. В одну кучку кладется буки, в другую бяки. Игроки договариваются какие ходы разрешены, обычно их два: можно забрать несколько бук и добавить несколько бяк или наоборот. При этом добавляется фигур всегда меньше, чем забирается, в этом тайный смысл  — количество неудач и огорчений должно уменьшаться с каждым ходом. Кто не сможет сделать очередной ход  — проиграл.

 — С удовольствием сыграю с Вами! Что-то много в моей жизни стало неудач, вдруг поможет?

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

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и b — начальное количество бук и бяк. Вторая строка входного файла содержит два натуральных числа, записанных через пробел: x₁ и y₁ — описание первого хода, при котором из кучки бук удаляется x₁ фигур, а в кучку бяк добавляется y₁ фигур. Третья строка входного файла содержит два натуральных числа, записанных через пробел: x₂ и y₂ — описание второго хода, при котором в кучку бук добавляется x₂ фигур, а из кучки бяк удаляется y₂ фигур.

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

Выведите "Watson" или "Rucastle" (без кавычек) — имя победителя при данных правилах игры. Первый ход всегда делает доктор Ватсон.

Ограничения

1 ≤ a, b, x₁, x₂, y₁, y₂ ≤ 500

y₁ < x₁

x₂ < y₂

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

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

На рисунке ниже приведено дерево ходов. Независимо от выбора первого хода доктора Ватсона, все остальные ходы будут единственно возможными. После того, как на поле останется одна фигура, ни одного хода сделать будет нельзя. Победит мистер Рукасл.

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

2 3
2 1
1 2

Rucastle

Задача V. ЭлементАРно, Ватсон! ≡

Условие

У этой задачи нет условия…, но познания Шерлока Холмса в этой области — глубокие.

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

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

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

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

Ограничения

1 ≤ n ≤ 15

1 ≤ m_i ≤ 127

Система оценки и описание подзадач

Баллы за задачу начисляются только в случае, если все тесты успешно пройдены.

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

1
102

no

11
6 1 95 15 53 8 7 16 1 53 15

championship

6
16 127 73 7 22 13

substantial

Задача W. Три субъекта ≡

Условие

Какому мальчишке не хотелось хоть на минутку примерить славу великого сыщика? В этой задаче у вас появится шанс стать Шерлоком Холмсом! Хотя бы в рамках формальной логики...

Итак, у нас классическая детективная ситуация — трое подозреваемых (обозначим их A, B и C), ровно один из них виновен. Каждый из троих высказал одно предположение о виновности или невиновности одного из этих трех человек. Естественно, тот, кто виновен — солгал, те кто невиновны — сказали правду.

Обозначим A высказывание "A виновен" (аналогично B означает высказывание "B виновен", C означает высказывание "C виновен").

Обозначим  − A высказывание "A невиновен" (аналогично  − B означает высказывание "B невиновен",  − C означает высказывание "C невиновен").

По данным высказываниям сузьте круг подозреваемых (если это возможно).

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

Единственная строка входного файла содержит три закодированных высказывания, записанных через пробел. Первое из них высказал A, второе — B, третье — C. Гарантируется непротиворечивость входных данных.

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

Выведите в лескикографическом порядке символы A, B и C — оставшихся подозреваемых (без пробелов).

Ограничения

Дополнительных ограничений нет.

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере A обвиняет B, B и C обвиняют A.

Предположим, что виновен A. Тогда он сказал неправду, двое остальных — правду. Нет противоречия, A может быть виновен.

Предположим, что виновен B. Тогда он солгал, A сказал правду, а C солгал. Солгали двое. Получили противоречие, B не может быть виновен.

Предположим, что виновен C. Тогда солгали все трое. Получили противоречие, C не может быть виновен.

Вывод — виновным может быть только A.

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

В третьем примере все подозреваемые заявляют о собственной невиновности. Никаких дополнительных выводов сделать нельзя.

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

B A A

A

C -B -C

AC

-A -B -C

ABC

Задача X. Скобки Брюса-Партингтона ≡

Условие

Мы с моим другом ждали, что Майкрофт скажет дальше.

 — Вы, конечно, знаете о шифрах Брюса-Партингтона?

 — Только понаслышке.

 — Трудно переоценить их военное значение. Из всех государственных тайн эта охранялась особенно ревностно. И вдруг мы находим их в кармане мертвого мелкого чиновника, в центре города! С политической точки зрения это просто ужасно.

Шифр Брюса-Партингтона был основан на симметричных правильных скобочных последовательностях. Правильная скобочная последовательность (ПСП) — строка, состоящая из символов "(" и ")", построенная по определенным правилам:

1) Пустая строка — ПСП;

2) Если a — ПСП, то (a), ()a и a() — тоже ПСП.

ПСП считается симметричной при выполнении следующего условия: если i-м месте с начала строки стоит символ (, то на i-м месте с конца строки стоит символ ) и наоборот. Все симметричные ПСП одной длины шифровальщик расположил в лексикографическом порядке. Помогите ему быстро узнать, какая последовательность расположена на k-й позиции.

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

Единственная строка входного файла содержит два натуральных числа, записанных через пробел: n и k — длина ПСП и порядковый номер. Гарантируется четность n и корректность k.

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

Выведите одну строку — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 40

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснения к примерам

В первом примере полный набор симметричных ПСС состоит из трёх строк: ((())), (()()) и ()()(). Лексикографически открывающая скобка меньше закрывающей, поэтому на втором месте находится указанная в ответе ПСС.

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

6 2

(()())

12 18

()(())(())()

Задача Y. Предпоследнее дело Холмса ≡

Условие

С тяжелым сердцем приступаю я к последним строкам этих воспоминаний, повествующих о необыкновенных талантах моего друга Шерлока Холмса. Его трагическая гибель в Рейхенбахском водопаде до сих пор не дает мне покоя. По совету миссис Хадсон я постарался перенести события тех дней на бумагу. К сожалению, при публикации в "Стрэнде", редакторы не включили один эпизод из моей рукописи, посчитав его незначительным. Но на мой взгляд, Холмс в этом расследовании проявил недюжинные аналитические способности, заслуживающие того, чтобы с ними познакомилась широкая публика.

Эта история произошла в поезде, когда мы уже мчались по континенту, радуясь, что ускользнули от Мориарти. В Европе пассажирское сообщение совершенно не похоже на наше. Начать с того, что в вагоне было ровно n одноместных купе. Мы с Шерлоком заняли два соседних и всю ночь проспали, не просыпаясь. Утром меня разбудил шум в коридоре. Когда я вышел, мой друг вкратце рассказал, что случилось.

 — Убийство, Ватсон! Кто-то зарезал беднягу из последнего купе, пока тот спал. Тело обнаружил проводник. Я уже осмотрел место преступления — никаких следов.

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

Мы склонились над листом с числами. Я тоскливо созерцал аккуратную запись, сделанную синими чернилами: 1 2 8 1 8 2, не в силах понять, как её можно использовать в расследовании. Внезапно Холмс радостно потер руки.

 — Смотрите, друг мой! В вагоне всего восемь купе. Мы с вами ехали в третьем и четвертом и ночью не выходили. Постараемся представить, как развивались события. Вот открывается дверь первого купе и пассажир №1 выходит в коридор. Далее открывается дверь второго купе и пассажир №2 тоже выходит в коридор. Наконец, открывается дверь последнего купе, убийца заходит в купе жертвы и закрывает за собой дверь. Это либо №1, либо №2 — в коридоре сейчас только они. Но далее опять открывается дверь первого купе — это пассажир №1 возвращается назад. Потом опять открывается дверь последнего купе и убийца возвращается к себе. Нужно навестить второе купе, у меня есть вопросы к его обитателю!

 — А может быть, они действовали сообща?

 — Все возможно, милый доктор! Но пока наш главный подозреваемый — пассажир №2 и он может быть опасен! У Вас пистолет с собой?

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n — количество купе в вагоне и m — количество чисел на листочке проводника. Во второй строке через пробел расположено m натуральных чисел k_i. Гарантируется, что каждое число присутствует во второй строке четное число раз (пассажир мог выходить в коридор и возвращаться неоднократно). Гарантируется, что число n присутствует во второй строке ровно два раза.

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

Выведите через пробел в порядке возрастания все номера купе, пассажиры которых по логике Холмса являются главными подозреваемыми. Гарантируется, что хотя бы один пассажир был в коридоре в момент первого открытия двери последнего купе. Гарантируется, что хотя бы один пассажир вернулся к себе после второго открытия двери последнего купе.

Ограничения

4 ≤ n, m ≤ 10⁵

1 ≤ k_i ≤ n

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

Первый пример разобран в тексте задачи.

Во втором примере пассажир №3 не находился в коридоре в момент проникновения в последнее купе, а пассажиры №4 и №5 вышли из своих купе уже после этого. Основные подозреваемые — пассажиры №1 и №2, любой из них мог совершить преступление.

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

8 6
1 2 8 1 8 2

2

8 16
1 2 3 2 3 2 8 4 5 8 3 1 2 3 5 4

1 2

Задача Z. Его прощальный брутфорс ≡

Условие

— Чтобы открыть такой замок, требуется знать определенное слово и определенное число. — Фон Борк поднялся и показал на двойной диск вокруг замочной скважины.

— Здорово, здорово!

— Не так-то просто, как вы думали. Я заказал его четыре года назад, и, знаете, какие я выбрал слово и число?

— Понятия не имею.

— Так вот, слушайте: слово — «август», а число — 1914, поняли?

Лицо американца выразило восхищение.

— Вот это ловко, ей-Богу! То есть в самый раз угадали! — воскликнул он удивленно. — Но с точки зрения информационной безопасности такой код никуда не годится. Нет, если перебирать все возможные коды по порядку, тратя на проверку каждого ровно одну секунду, то пока доберешься до задуманного Вами пароля, придется крутить ручки около 3000 лет без перерыва. Но когда видишь буквы и цифры на панели сейфа, резонно предположить, что задумана определенная дата и тогда добраться до неё гораздо проще.

— Из местных тупиц-полицейских до такого ни додумается никто... Шерлок Холмс бы, пожалуй, смог, но о нём уже несколько лет ни слуху, ни духу. Так кого мне бояться?

Не говоря ни слова, американец передал пакет. Фон Борк развязал бечевку, развернул два слоя оберточной бумаги. Несколько мгновений он не сводил изумленного взгляда с небольшой книжки в синем переплете, на котором золотыми буквами было вытиснено «Практическое руководство по разведению пчел». Но долго рассматривать эту неуместную надпись ему не пришлось: руки крепкие, словно железные тиски, охватили сзади его шею и прижали к его лицу пропитанную хлороформом губку.

По данному коду определите, каким по счету он будет проверен при полном переборе. Коды проверяются в лексикографическом порядке.

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и b  — длины строковой и числовой частей кода сейфа. Во второй строке приведен сам код, состоящий из a строчных английских букв в начале и b десятичных цифр в конце.

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

Выведите одно натуральное число  — каким по счету будет проверен данный код. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

1 ≤ a, b ≤ 10

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при a = 1 и b = 1, получат не менее 20 баллов.

Решения, верно работающие при a = 1, получат не менее 20 баллов.

Пояснение к примерам

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

Во втором примере сначала переберут 10 кодов, начинающихся на букву "a" (от a0 до a9), потом пять кодов, начинающихся на "b" (от b0 до b4).

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

2 3
aa000

1

1 1
b4

15

2 2
bb22

2723

6 4
august1914

92589831915