Задача A. Илья Муромец ≡

Условие

Известно, что Илья Муромец пролежал на печи ровно x лет и еще ⌊ x10⌋ года (здесь ⌊ x10⌋ означает x деленное на 10 и округленное вниз до целой части). По известному общему числу лет бездействия богатыря n определите x.

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

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

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

Выведите два неотрицательных целых числа — x и ⌊ x10⌋, таких, что их сумма в точности равна n. Если такой пары чисел не существует, выведите одно число  − 1.

Ограничения

1 ≤ n ≤ 10¹⁸

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

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

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

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

В первом примере для числа 32 подходящей пары чисел нет.

Во втором примере тридцать три года можно представить в виде суммы чисел 30 и 3. При этом ⌊ 3010⌋  = 3.

В третьем примере тридцать четыре года можно представить в виде суммы чисел 31 и 3. При этом ⌊ 3110⌋  = 3.

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

32

-1

33

30 3

34

31 3

Задача B. Добрыня Никитич ≡

Условие

 — А еще, Добрыня, запомни, отрубишь у Змея Горыныча h голов  — на их месте сразу же 2 × h + 1 голов вырастет! А как окажется у Змея ровно p голов  — тут-то он и помрет!"  — напутствовала богатыря Василиса Премудрая.

И вот встретились в чистом поле Добрыня Никитич и n-головый Змей Горыныч. Сможет ли былинный герой одолеть хтоническое чудовище?

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

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

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

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

Ограничения

1 ≤ n < p ≤ 10¹²

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

В примере дан трехголовый Змей Горыныч. Первым ударом богатырь срубает две головы и Змей становится шестиголовым. Вторым ударом богатырь срубает все шесть голов, Змей становится тринадцатиголовым и умирает. Есть и другие способы погубить чудовище.

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

3 13

Yes

Задача C. Алёша Попович ≡

Условие

 — Нельзя тебе, Алёшенька, в логово разбойничье вот так вот соваться! Узнают тебя душегубы  — навалятся гурьбой, да и одолеют! Тут хитростью нужно действовать, чтобы до самого Соловья добраться, — вслух рассуждала Василиса Премудрая.  — Есть у меня зелье одно, что внешность меняет, от Золушки осталось, примешь его — никто тебя не узнает.

 — И имя новое тогда мне придумай.

 — Это несложно. Можно гласные буквы заменить на гласные, но в другом порядке: не с начала алфавита, а с конца. И с согласными то же самое сделать. Вот был ты Popovich, а будешь Lilifoxs. За гостя заграничного сойдешь, который с Соловьем хочет международный договор заключить по обмену опытом воровским. А уж как окажешься с главарем один на один  — бей его и в рог труби, а другие богатыри тебе на выручку бросятся!

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

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

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

Выведите строку из строчных английских букв, в котором каждая гласная буква из входных данных (aeiouy) заменяется на букву из этого же набора, но в порядке от конца алфавита. То есть, буква a меняется на y, буква e меняется на u, буква i меняется на o, буква o меняется на i, буква u меняется на e, буква y меняется на a. По такому же принципу меняются согласные буквы.

Ограничения

1 ≤ len(s) ≤ 255

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

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

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

popovich

lilifoxs

Задача D. Баба Яга и волшебные часы ≡

Условие

Говорят, что у Бабы Яги есть волшебные механические часы, висящие напротив печки. Поскольку время в Зачарованном лесу идет не так, как на остальной земле, циферблат часов разбит на n секторов, обозначенных числами от 1 до n.

И если разбить циферблат часов мечом-кладенцом на две части таким образом, чтобы суммы чисел на обеих частях были равны, то лишится Баба Яга всей своей магической силы. Да вот только возможно ли это?

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

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

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

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

Ограничения

2 ≤ n ≤ 10⁵

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

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

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

Решения, верно определяющие, при каких n ответ гарантированно будет равен нулю, получат не менее 20 баллов.

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

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

В первом примере дано n = 3. В одной части останутся числа 1 и 2, в другой — 3. Суммы равны, других решений нет.

Во втором примере n = 5. Нет никаких способов разбить набор чисел от 1 до 5 на две равные по сумме части.

Во третьем примере n = 8. Есть два решения:

Первое: 3, 4, 5 и 6 по одну сторону отрезка и 7, 8, 1 и 2 по другую.

Второе: 5, 6 и 7 по одну сторону отрезка и 8, 1, 2, 3 и 4 по другую. Во всех случаях суммы чисел равны 18.

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

3

1

5

0

8

2

Задача E. Замок Кащея Бессмертного ≡

Условие

Спроектированный Кащеем замок состоит из башен, в i-й по счету башне находится i² комнат, по одной на каждом этаже. Нумерация комнат соответствует представленной на рисунке. На каком этаже расположена комната с номером n, где томится Василиса Прекрасная?

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁸

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

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

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

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

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

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

50

20

Задача F. Погоня за Идолищем Поганым ≡

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁸

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

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

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

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

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

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

46

15 -1

Задача G. Три богатыря ≡

Условие

Три богатыря бьются со Змеем Горынычем. Илья Муромец каждым своим ударом отрубает Змею половину всех голов и еще одну, Добрыня Никитич — треть всех голов и еще одну, Алеша Попович — четверть всех голов и еще одну. Богатыри бьют по одному в каком хотят порядке, отрубая каждым ударом целое число голов. Если ни один богатырь не может ударить (число голов получается нецелым), Змей съедает всех троих. Смогут ли богатыри отрубить все головы Змею? Какое минимальное количество ударов им понадобится?

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

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

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

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

В примере у Змея 10 голов. Первый удар наносит Илья Муромец и отрубает 5 + 1 голову. Второй удар наносит Алеша Попович и отрубает у четырехглавого змея 1 + 1 голову. Последний удар наносит Илья Муромец и отрубает у двуглавого змея 1 + 1 голову. Всего потребовалось три удара.

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

10

3

Задача H. Тридцать три богатыря ≡

Условие

Дядька Черномор очень любит расставлять своих богатырей в колонны и шеренги. Его расстраивает одно — количество расстановок не очень велико. В самом деле: всех богатырей можно выстроить в одну шеренгу, в три шеренги, в три колонны и в одну колонну, всего четыре способа! А Черномору хочется ровно n способов! Помогите ему определить минимальное количество богатырей, необходимое для этого.

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

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

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

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

Ограничения

2 ≤ n ≤ 26

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

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

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

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

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

5

16

Задача I. Триста тридцать три богатыря ≡

Условие

Триста спартанцев и тридцать три богатыря решили действовать сообща. Царь Леонид и дядька Черномор после долгих поисков, проб и ошибок, наконец определили наиболее боеспособные построения объединенной команды. В первом из них трое богатырей образуют вершины равностороннего треугольника, а несколько спартанцев (не менее одного) находятся на стороне этого треугольника (поровну на каждой из сторон). Во втором построении четверо богатырей образуют вершины квадрата, а несколько спартанцев (не менее одного) находятся на стороне этого квадрата (опять же, поровну на каждой из сторон). Таких одинаковых треугольников и квадратов может быть сколь угодно много (а может и не быть совсем).

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

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

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

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

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

Ограничения

3 ≤ b ≤ s ≤ 1000

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

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

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

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

В примере 33 богатыря и 300 спартанцев. Существует несколько возможностей расставить всех воинов требуемым образом. Вот одна из них:

На каждой стороне треугольника находится 12 спартанцев. Всего таких треугольников будет три.

На каждой стороне квадрата находится 8 спартанцев. Всего таких квадратов будет шесть.

Итого расставлено 3 × 3 + 4 × 6 = 9 + 24 = 33 богатыря и 3 × 12 × 3 + 4 × 8 × 6 = 108 + 192 = 300 спартанцев.

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

33 300

Yes

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

Условие

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

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

...

А Марфа Васильевна пробормотала:

 — Да куда им! Да где им! Эти лентяи до семидесяти семи и сосчитать не сумеют, сразу собьются.

Евгений Шварц, "Сказка о потерянном времени", 1940 г.

Чтобы не сбиться, Маруся Поспелова отмечала на листочке, сколько раз Петя Зубов повернул стрелки на полный круг. Делала она это при помощи особой системы записи чисел (смотри рисунок), которой её научила бабушка-библиотекарь. По имеющейся записи определите, сколько ещё полных оборотов нужно сделать Пете.

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

Три строки равной длины входных данных содержат запись натурального числа n в библиотечной системе записи чисел. Используются символы . (ASCII-код 46), - (ASCII-код 45), | (ASCII-код 124), / (ASCII-код 47), X (ASCII-код 88) и пробел (ASCII-код 32). Гарантируется корректность записи. Все строки не заканчиваются пробелами одновременно.

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

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

Ограничения

1 ≤ n ≤ 76

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

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

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

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

В первом примере записано число 39. Пете осталось сделать 38 оборотов.

Во втором примере записано число 12. Пете осталось сделать 65 оборотов.

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

.-. .-. .-. .-.
|X| |X| |X| |/|
.-. .-. .-. .-.

38

.-.    
|X|    
.-. . .

65

Задача K. Мёртвая вода ≡

Условие

На полке у Кащея стоят бутылки с водой объёмом от 1 до n. Иван-царевич знает, что мёртвая вода только в тех ёмкостях, сумма цифр объёма которых равна 13. Кащей разрешил герою взять только одну бутылку. Какой наибольший объём мёртвой воды может получить Иван-царевич?

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

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

Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

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

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

Ограничения

50 ≤ n ≤ 10¹⁸

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

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

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

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

В примере дано n = 150. Мёртвая вода в бутылках объемом 49, 58, 67, 76, 85, 94, 139 и 148. Наибольший подходящий объём — 148.

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

150

148

Задача L. Живая вода ≡

Условие

На полке у Бабы Яги стоят бутылки с водой объёмом от 1 до n. Иван-царевич знает, что живая вода только в тех ёмкостях, объём которых содержит хотя бы одну цифру 7. Сколько бутылок с живой водой у Бабы Яги?

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

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

Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

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

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

Ограничения

1 ≤ n ≤ 10¹⁸

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

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

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

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

В примере дано n = 20. Живая вода в бутылках объемом 7 и 17.

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

20

2

Задача M. Распределяющая шляпа ≡

Условие

В школе чародейства и волшебства Хогвартс четыре факультета (обозначим их числами от 1 до 4).

В результате последних приказов Министерства магии по оптимизации учебного процесса и равномерного распределения нагрузки среди преподавателей школы, алгоритм работы Распределяющей шляпы теперь описывается следующим набором правил:

1) Очередной абитуриент зачисляется на факультет, в котором меньше всего студентов. Если таких факультетов несколько, зачисление производится на факультет с наименьшим номером.

2) Запрещается двух абитуриентов подряд зачислять на один и тот же факультет. Если факультет, в который был зачислен предыдущий абитуриент по прежнему имеет в своём составе меньше всего студентов, зачисление производится на тот факультет из трёх оставшихся, в котором меньше всего студентов (при равенстве опять-таки выбирается факультет с меньшим номером).

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

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

Четыре строки входных данных содержат четыре неотрицательных целых числа: a, b, c и d.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

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

Ограничения

1 ≤ a, b, c, d ≤ 10¹⁵

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

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

Решения, верно работающие при max(a, b, c, d) ≤ 1000, получат не менее 50 баллов.

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

В первом примере на всех факультетах равное число студентов. Новых абитуриентов принимать не нужно.

Во втором примере распределение будет происходить следующим образом:

Первый абитуриент распределяется на факультет №2 (там меньше всего студентов). Теперь на факультетах 3, 1, 1 и 2 студента.

Второй абитуриент распределяется на факультет №3 (есть 2 факультета с наименьшим числом студентов: №2 и №3, но №2 снова выбрать нельзя). Теперь на факультетах 3, 1, 2 и 2 студента.

Третий абитуриент распределяется на факультет №2. Теперь на факультетах 3, 2, 2 и 2 студента.

Четвёртый абитуриент распределяется на факультет №3 (есть 3 факультета с наименьшим числом студентов: №2, №3 и №4, но №2 снова выбрать нельзя, а у №3 номер меньше, чем у №4). Теперь на факультетах 3, 2, 3 и 2 студента.

Пятый абитуриент распределяется на факультет №2 (есть 2 факультета с наименьшим числом студентов: №2 и №4, но у №2 номер меньше, чем у №4). Теперь на факультетах 3, 3, 3 и 2 студента.

Шестой абитуриент распределяется на факультет №4. Теперь на факультетах равное число студентов.

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

1
1
1
1

0

3
0
1
2

6

5
0
4
4

11

Задача N. Щучье веленье ≡

Условие

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

Николай Лесков, "Соборяне", 1872 г.

Как Вы помните, первым желанием Емели стало самостоятельное передвижение в направлении дома двух вёдер с водой "да чтоб не расплескалось". Однако, в соответствии с законом о сохранении материи, открытом профессором химии М.В. Ломоносовым примерно в это же время, часть воды неизбежно должна тратиться во время движения. Магическое правило такое: с каждым шагом из первого ведра исчезает столько капель жидкости, чему равна последняя цифра числа капель во втором ведре. Аналогично, при этом же шаге из второго ведра исчезает столько капель жидкости, чему равна последняя цифра числа капель в первом ведре.

По известной длине пути и начальной заполненности вёдер определите, сколько воды Емеля доставит до дома "по щучьему велению".

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

Первые две строки входных данных содержат натуральные числа a и b — начальное количество воды (в каплях) в вёдрах. Третья строка содержит натуральное число n — расстояние до дома в шагах.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

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

Ограничения

1 ≤ a, b, n ≤ 10¹⁶

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

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

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

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

В примере дано: в первом ведре в начале пути было 15 капель, во втором — 26. Дом Емели находится "в двух шагах".

• После первого шага в первом ведре останется 15 − 6 = 9 капель, во втором 26 − 5 = 21 капля воды;
• После второго шага в первом ведре останется 9 − 1 = 8 капель, во втором 21 − 9 = 12 капель.

Всего до дома доставлено 12 + 8 = 20 капель жидкости.

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

15
26
2

20

Задача O. Меч-кладенец ≡

Условие

...

Сколько девичьих в воду упало колец,

Сколько бед натерпелось от Лиха-злодея!

Но вступился за правду удал-молодец.

И срубил в душном логове меч-кладенец

Семь голов у проклятого Змея.

...

Всеволод Рождественский, "Русская сказка", 1962 г.

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

Меч, доставшийся Всеволоду, требовал, чтобы в бою со Змеем богатырь первым ударом срубил чудищу любое натуральное число голов, а каждым следующим — на 1 или 2 больше, чем предыдущим. Определите количество способов победить n-голового Горыныча, нанеся ровно k ударов.

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

Две строки входных данных содержат два натуральных числа: n и k.

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

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

Ограничения

3 ≤ n ≤ 1000

2 ≤ k ≤ 20

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

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

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

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

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

В первом примере существует единственная подходящая последовательность, позволяющая одолеть семиголового Змея за три удара: 1, 2, 4.

Во втором примере существует две подходящие последовательности: 1, 2, 4, 6 и 1, 3, 4, 5.

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

7
3

1

13
4

2

Задача P. Шапка-невидимка ≡

Условие

Я был в избушке на курьих ножках.

Там всё как прежде. Сидит Яга.

Пищали мыши, и рылись в крошках.

Старуха злая была строга.

Но я был в шапке, был в невидимке.

Стянул у Старой две нитки бус.

Разгневал Ведьму, и скрылся в дымке.

И вот со смехом кручу свой ус.

Пойду, пожалуй, теперь к Кощею.

Найду для песен там жемчугов.

До самой пасти приближусь к Змею.

Узнаю тайны — и был таков.

Константин Бальмонт, "У чудищ", 1905 г.

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

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

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

• Символ . (ASCII-код 46) — обычная клетка, свободная для посещения;
• Символ # (ASCII-код 35) — стена, клетка, в которую нельзя перемещаться;
• Символ K (ASCII-код 75) — клетка, в которой Константин находится в начале исследования лабиринта (одна на весь лабиринт);
• Символ A (ASCII-код 65) — клетка, в которой находится артефакт (может быть несколько или ни одной), свободная для посещения;
• Символ B (ASCII-код 66) — клетка, в которой находится чудище (может быть несколько или ни одной).

Выходить за пределы лабиринта нельзя.

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

Выведите одно неотрицательное целое число — количество артефактов, которые сможет собрать Константин.

Ограничения

5 ≤ n, m ≤ 250

1 ≤ d ≤ 10

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

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

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

12 20
.........#....A.....
.K.....############.
.......#...........#
....................
.A..................
...B................
.........B....B.....
################....
.....#....#.........
...A.#....#######...
.....#.#....#.#.###.
.......###..........
3

1

Задача Q. Ковёр-самолёт ≡

Условие

Только ночью ковёр-самолёт можно испытать как следует. А если днём — представляете, какой шум поднимется в городе!

Владислав Крапивин, "Ковер-самолет", 1976 г.

Пробный полёт ковра-самолёта запланирован на эту ночь. Маршрут определён заранее: нужно пролететь по периметру треугольника с заданными вершинами. Для лучшей ориентации необходимо в каждой точке маршрута с целочисленными координатами зажечь сигнальный огонь. Определите количество огней, которые нужно зажечь.

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

Три строки входных данных содержат по два целых числа, записанных через пробел: x_i, y_i — координаты вершины треугольника. Гарантируется, что треугольник невырожденный.

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

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

Ограничения

 − 10⁹ ≤ x_i, y_i ≤ 10⁹

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

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

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

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

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

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

0 0
3 9
17 2

11

Задача R. Скатерть-самобранка ≡

Условие

... Был

Обед такой, какого никогда

Никто не слыхивал: уха, как жидкий

Янтарь, сверкавшая в больших кастрюлях;

Огромножирные, длиною в сажень

Из Волги стерляди на золотых

Узорных блюдах; кулебяка с сладкой

Начинкою, с груздями гуси, каша

С сметаною, блины с икрою свежей

И крупной, как жемчуг, и пироги

Подовые, потопленные в масле;

А для питья шипучий квас в хрустальных

Кувшинах, мартовское пиво, мед

Душистый и вино из всех земель:

Шампанское, венгерское, мадера,

И ренское, и всякие наливки  —

Короче молвить, скатерть-самобранка

Так отличилася, что было чудо.

...

Василий Жуковский, "Сказка об Иване-царевиче и Сером Волке", 1845 г.

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

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

Единственная строка входных данных содержит натуральное число k.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

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

Ограничения

1 ≤ k ≤ 5 × 10⁸

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

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

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

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

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

В примере дано k = 3. Существует 5 подходящих прямоугольников с нужным значением k (смотри таблицу). Самая большая разница между длиной и шириной у первого прямоугольника.

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

3

7
42

Задача S. Неразменный пятак ≡

Условие

Эксперимент занял у меня около часа. За этот час я десять раз обошел площадь кругом, разбух от воды, спичечных коробков и газет, перезнакомился со всеми продавцами и продавщицами и пришел к ряду интересных выводов. Пятак возвращается, если им платить. Если его просто бросить, обронить, потерять, он останется там, где упал. Пятак возвращается в карман в тот момент, когда сдача из рук продавца переходит в руки покупателя. Если при этом держать руку в одном кармане, пятак появляется в другом. В кармане, застегнутом на «молнию», он не появляется никогда. Если держать руки в обоих карманах и принимать сдачу локтем, то пятак может появиться где угодно на теле (в моем случае он обнаружился в ботинке). Исчезновение пятака из тарелочки с медью на прилавке заметить не удается: среди прочей меди пятак сейчас же теряется, и никакого движения в тарелочке в момент перехода пятака в карман не происходит.

Аркадий и Борис Стругацкие, "Понедельник начинается в субботу", 1965 г.

По сюжету книги, Александр Привалов вступил в обладание действующей моделью неразменного пятака образца ГОСТ 718–62 и злоупотребил ею. Он совершил n покупок и каждый раз, отдавая продавцу одну лишь волшебную монетку, получал сдачу (напомним, что в те годы, помимо пятаков, в ходу были мелкие монеты достоинством 1, 2 и 3 копейки).

Позже, в милиции, у задержанного Привалова обнаружили в кармане x трёхкопеечных и y двухкопеечных монет. Считая, что утром у Александра в кармане был только неразменный пятак, определите наименьшее и наибольшее возможное количество однокопеечных монет у главного героя на момент задержания.

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

Первая строка входных данных содержит натуральное число n — количество покупок, совершённых Александром. Во второй и третьей строке расположены неотрицательные целые числа x, y — количество трёх~ и двухкопеечных монет соответственно. Гарантируется непротиворечивость входных данных.

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

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

Ограничения

1 ≤ n ≤ 10⁹

0 ≤ x ≤ n

0 ≤ y ≤ 2 × n

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

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

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

В примере Александр совершил одну покупку и получил сдачу, содержащую монетку в 3 копейки. Если товар стоил 2 копейки (номер местной газеты «Рыбак»), то ни одной монетки достоинством 1 копейка у него не окажется, а если товар стоил 1 копейку (коробок спичек), то сдача составит одну монетку в 3 копейки и одну монетку в 1 копейку.

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

1
1
0

0 1

Задача T. Сердце горы ≡

Условие

Хоббит и гномы наконец-то добрались до Одинокой горы. Логово Смауга имеет форму треугольника, высотой n этажей, и разбито на n² равных пронумерованных треугольных комнат (смотри рисунок). Бильбо может свободно перемещаться между комнатами, соблюдая три правила:

1) нельзя подниматься на этаж выше того, на котором сейчас находишься;

2) нельзя возвращаться в комнату, в которой уже побывал.

3) можно переместиться в комнату, если она имеет общую сторону с той, в которой сейчас находишься, если это не противоречит предыдущим правилам.

Для каждой комнаты известно количество золотых монет, находящихся в ней. Также в комнате номер d находится дракон. Вор-взломщик начинает в самой верхней комнате и заканчивает свой путь в любой из нижних (на рисунке слева изображен один из допустимых маршрутов). Какое наибольшее количество монет он сможет собрать? Естественно, маршрут хоббита не должен включать комнату с драконом.

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

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

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

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

Ограничения

2 ≤ n ≤ 100

1 ≤ x_i ≤ 10⁹

2 ≤ d ≤ 100

d ≠ 3

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

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

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

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

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

В примере маршрут хоббита будет включать комнаты 1, 3, 4, 8 и 9. Если бы дракон находился в комнате 2, можно было бы собрать 34 монеты, посетив комнаты 1, 3, 4, 8, 7, 6 и 5

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

3
1 2 3 4 5 6 7 8 9
7

25

Задача U. Гусли-самогуды ≡

Условие

...

"Ox, Терентий-муж, Данилович,

Тяжело мне, нету моченьки!"  —

Говорит она, вздыхаючи,

На него уставя оченьки.

 —Ты сходи-ка в ту сторонушку,

Где игрой гусляры славятся;

Пусть меня потешат песнями,  —

Может, немочь и убавится».

Молодой жене Данилович

Не перечит, собирается;

Взявши шапку, за гуслярами

В дальний город отправляется.

...

Иван Суриков "Немочь", 1873 г.

Терентию нужно как можно быстрее догнать бродячих артистов с волшебными гуслями-самогудами, чтобы спасти умирающую супругу. Его дом на координатной плоскости расположен в точке (0, a). Повозка трубадуров в момент выхода заботливого мужа из дома находится в точке (0, 0) и движется вдоль оси абсцисс с постоянной скоростью V₁.

Помогите Терентию определить координаты точки, в которой он догонит гусляров, если будет двигаться с постоянной скоростью V₂.

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

Три строки входных данных содержат три натуральных числа: a, V₁ и V₂.

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

Выведите ответ на вопрос задачи с точностью не менее 3 знаков после запятой. Гарантируется, что входные данные таковы, что ответ не превысит 10⁹.

Ограничения

1 ≤ a ≤ 10⁹

1 ≤ V₁ < V₂ ≤ 1000

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

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

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

В примере дано a = 4, V₁ = 5 и V₂ = 6. В точку с координатами (6.030226..., 0) герои задачи доберутся одновременно.

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

4
5
6

6.030226891555273

Задача V. Яблочко на блюдечке ≡

Условие

Блюдечко разделено на 360 секторов (они пронумерованы по порядку от 1 до 360). Согласно инструкции по использованию наливного яблочка, его сначала требуется установить так, чтобы хвостик (плодоножка) указывал на число 360. Затем яблоко требуется запустить с некоторой натуральной угловой скоростью хвостика. Яблоко катится с указанной скоростью ровно t секунд, после чего останавливается и показывает, что происходит в одной из 360 мировых столиц (в зависимости от того, на какое число укажет хвостик).

Чтобы царёвы дочери не заглядывались на иноземных женихов, придворный чародей Чернодзор ограничил скорость яблока — теперь оно не превышает v градусов в секунду. Сколько мировых столиц осталось доступно для просмотра?

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

Две строки входных данных содержат два натуральных числа v и t.

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

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

Ограничения

1 ≤ v, t ≤ 10⁹

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

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

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

В примере дано v = 5 и t = 123.

Если запустить яблоко со скоростью 1° в секунду, то через 123 секунды хвостик яблока укажет на число 123.

Если запустить яблоко со скоростью 2° в секунду, то через 123 секунды хвостик яблока укажет на число 246.

Если запустить яблоко со скоростью 3° в секунду, то через 123 секунды хвостик яблока укажет на число 9.

Если запустить яблоко со скоростью 4° в секунду, то через 123 секунды хвостик яблока укажет на число 132.

Если запустить яблоко со скоростью 5° в секунду, то через 123 секунды хвостик яблока укажет на число 255.

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

5
123

5
9 123 132 246 255

Задача W. Гуси-лебеди ≡

Условие

Летят перелетные птицы

Ушедшее лето искать.

Летят они в жаркие страны,

А я не хочу улетать,

...

Михаил Исаковский, "Летят перелетные птицы", 1948 г.

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

Всего в стае нечётное число птиц n, каждой птице присвоено число от 1 до n — её сила. Самый сильный гусь (с силой n) полетит во главе косяка, слева от него — следующий по силе (n − 1), а справа — птица с силой (n − 2). И так далее: следующие пары гусей распределятся слева и справа от уже сформировавшегося косяка.

По известной численности птиц нарисуйте улетевший косяк.

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

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

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

Выведите n строк с заданным изображением. Используйте символы '.' (ASCII-код 46), '/' (ASCII-код 47), '\' (ASCII-код 92) и десятичные цифры.

Ограничения

3 ≤ n ≤ 99

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

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

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

7

......7......
...../.\.....
....6...5....
.../.....\...
..4.......3..
./.........\.
2...........1

23

.............................23............................
............................/..\...........................
..........................22....21.........................
........................./........\........................
.......................20..........19......................
....................../..............\.....................
....................18................17...................
.................../....................\..................
.................16......................15................
................/..........................\...............
..............14............................13.............
............./................................\............
...........12..................................11..........
........../......................................\.........
........10........................................9........
......./...........................................\.......
......8.............................................7......
...../...............................................\.....
....6.................................................5....
.../...................................................\...
..4.....................................................3..
./.......................................................\.
2.........................................................1