Задача 00. Наташа плюс Серёжа ≡

Условие

Тревожно и серьезно

Я вывел на снегу:

«Наташа + Серёжа»,

А дальше не могу.

...

Леонид Филатов, "Наташа плюс Серёжа", 1966 г.

Найдите сумму двух данных чисел.

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

Две строки входного файла содержат два целых числа: n и s.

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

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

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

Ограничения

 − 10¹⁵ ≤ n, s ≤ 10¹⁵

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

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

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

1
2

3

Задача 01. Удивительная кошка ≡

Условие

Несчастная кошка порезала лапу  —

Сидит, и ни шагу не может ступить.

Скорей, чтобы вылечить кошкину лапу

Воздушные шарики надо купить!

И сразу столпился народ на дороге  —

Шумит, и кричит, и на кошку глядит.

А кошка отчасти идет по дороге,

Отчасти по воздуху плавно летит!

Даниил Хармс, "Удивительная кошка", 1938 г.

У продавца воздушных шариков есть шары двух типов: маленькие, грузоподъемностью a, и большие, грузоподъемностью в b раз больше. Определите, какое наименьшее количество шариков нужно купить, чтобы их общая грузоподъемность была максимальной, но не превышающей вес кошки c?

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

Три строки входного файла содержат три натуральных числа a, b и c.

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

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

Ограничения

1 ≤ a ≤ 100

2 ≤ b ≤ 100

1 ≤ c ≤ 10⁹

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

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

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

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

В примере дано: грузоподъемность маленького шарика a = 2, большого — в b = 3 раза больше, то есть 6. Вес кошки 11.

Достаточно купить один большой и два маленьких шарика. Их общая грузоподъемность составит 10, что не превышает вес кошки.

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

2
3
11

1 2

Задача 02. Менеджер ≡

Условие

На американскую мечту сегодня мода

К этой мечте стремишься ты

Работать роботом, ради бумажной мечты

Ты менеджер среднего звена

Ты не работаешь под, ты работаешь на

Твой этот век, твоя компьютерная эра

Главное не человек, а его карьера

...

Сергей Шнуров, "Менеджер", 2003 г.

"Тебе повезло, ты не такой, как все — ты работаешь в офисе!" — напевает каждое утро Сергей. Слова не расходятся с делом: его новое место работы — старое офисное здание с одинаковой планировкой каждого этажа: в ряд расположено n офисов-кабинетов. Лифта в здании нет и поэтому сотрудникам приходится перемещаться между этажами по лестницам, расположенным по краям этажа. Первая лестница находится между первым и вторым офисом, вторая — между предпоследним и последним. Офис, где трудится Сергей, расположен на h_s-м этаже под номером n_s. Чтобы переместиться к соседнему офису или лестнице (если она примыкает к офису), Сергею нужно пройти a шагов, а чтобы подняться или спуститься по лестнице на один этаж — b шагов.

Сегодня Сергея в свой офис (этаж h_b, кабинет n_b) вызвал начальник отдела. Какое минимальное число шагов сделает Сергей прежде, чем узнает о новом поручении начальства?

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

Единственная строка входного файла содержит семь натуральных чисел, записанных через пробел: n, h_s, n_s, h_b, n_b, a и b. Гарантируется, что офисы Сергея и начальника отдела различны.

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

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

Ограничения

3 ≤ n ≤ 10⁸

1 ≤ n, h_s, n_s, h_b, n_b, a, b ≤ 10⁹

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

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

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

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

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

В примере дано здание с десятью офисами на каждом этаже. Кабинет Сергея расположен на первом этаже под номером 3, а офис начальника отдела на втором этаже под номером 4. Сергей выйдет из своего кабинета и дойдет до первой лестницы за 10 шагов (5 + 5), поднимется по лестнице на один этаж за 20 шагов и переместится до офиса начальника за 15 шагов. Всего потребуется 45 шагов. Путь, проходящий через вторую лестницу, существенно длиннее.

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

10 1 3 2 4 5 20

45

Задача 03. Москва – Петушки ≡

Условие

Чернота все плыла за окном и все тревожила. И будила чёрную мысль. Я стискивал голову, чтобы отточить эту мысль, но она всё никак не оттачивалась, а растекалась, как пиво по столу. «Не нравится мне эта тьма за окном, очень не нравится... ведь я выехал утром с Курского вокзала...»

«Да мало ли что утром!.. Теперь, слава Богу, осень, дни короткие; не успеешь очухаться — бах! уже темно... А ведь до Петушков ехать о-о-о как долго! От Москвы до Петушков о-о-о как долго ехать!..»

«Да чего "о-о-о"! Чего ты все "о-о-о" да "о-о-о"! От Москвы до Петушков ехать ровно два часа пятнадцать минут. В прошлую пятницу, например...»

Я взглянул за окно и опять нахмурился: «Да-а... странно всё-таки... выехали в восемь утра... и всё ещё едем...»

Венедикт Ерофеев, поэма "Москва — Петушки", 1969 г.

Электричка "Москва — Петушки" ходит по следующему расписанию: ровно в полночь она отправляется от Курского вокзала и через 2 часа и 15 минут прибывает в Петушки. В 4 часа утра она отбывает в обратный путь и еще через 2 часа и 15 минут возвращается в Москву. С такими же интервалами движения она отправляется из Москвы в 08:00 и в 16:00.

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

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

Единственная строка входного файла содержит строку символов, описывающую текущее время в формате hh:mm с ведущими нулями. Гарантируется корректность входных данных. Гарантируется, что текущее время не совпадает со временем отправления электропоезда в путь или прибытия на конечную станцию.

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

Выведите одну из четырёх строк (без кавычек) — ответ на вопрос задачи.

"Moscow" — если электричка в это время стоит на Курском вокзале.

"To Moscow" — если электричка в это время движется в сторону Москвы.

"Petushki" — если электричка в это время стоит на вокзале города Петушки.

"To Petushki" — если электричка в это время движется из Москвы.

Ограничения

00 ≤ hh ≤ 23

00 ≤ mm ≤ 59

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

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

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

В 20:00 электричка отправилась обратно в Москву, через час она будет всё ещё в пути.

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

21:00

To Moscow

Задача 04. Родная улица моя ≡

Условие

Когда весна придёт, не знаю,

Пройдут дожди... Сойдут снега...

Но ты мне, улица родная,

И в непогоду дорога.

...

На этой улице подростком

Гонял по крышам голубей,

И здесь, на этом перекрёстке,

С любовью встретился своей.

...

Алексей Фатьянов, "На Заречной улице", 1955 г.

Песня из фильма "Весна на Заречной улице"

На Заречной улице в один ряд расположено n домов, на крышах которых сидят d_i голубей. Сталевар-передовик Саша, пробегая вдоль домов, пугает птиц, которые перелетают на крыши следующих по порядку домов по такому правилу:

Пусть на крыше дома с номером i сидят d голубей. Поднявшись в воздух, они распределяются по крышам оставшихся n − i домов по ⌊ dn − i⌋ штук, где скобки означают округление вниз до целой части. Не делящийся остаток целиком перелетает на крышу следующего i + 1 дома. Для определенности считайте, что скорость птиц существенно превосходит скорость Саши и они успевают перераспределиться до того момента, когда он добежит до следующего дома.

Пробежав мимо первых m домов, молодой рабочий встретит на перекрестке выпускницу пединститута Таню, остановится как вкопанный, и в жизни пернатых наконец-то наступит спокойствие.

До входным данным определите итоговую рассадку птиц.

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

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

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

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

Выведите через пробел n − m неотрицательных целых чисел d_i — конечную рассадку голубей по крышам оставшихся домов.

Ограничения

1 ≤ m < n ≤ 10⁵

0 ≤ d_i ≤ 10⁹

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

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

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

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

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

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

В примере n = 5 домов. На крыше первого дома 10 голубей, второго — 0, третьего — 2, четвертого — 7 и пятого — 3. Саша пробежит мимо первых трех домов из пяти.

Первые десять голубей перелетят на крыши следующих четырёх домов. Так как ⌊ 104⌋  = 2, на каждую из следующих крыш перелетит по два голубя, а еще два (не делящийся остаток) перелетит на крышу следующего дома. Теперь голуби сидят так: 0, 4, 4, 9, 5.

Когда Саша будет пробегать мимо второго дома, четыре голубя перелетят на крыши следующих трёх домов. Так как ⌊ 43⌋  = 1, на каждую из следующих крыш перелетит по одному голубю, а еще один (не делящийся остаток) перелетит на крышу следующего дома. Теперь голуби сидят так: 0, 0, 6, 10, 6.

Когда Саша будет пробегать мимо третьего дома, шесть голубей перелетят на крыши следующих двух домов. Так как ⌊ 62⌋  = 3, на каждую из следующих крыш перелетит по три голубя. Не делящийся остаток равен нулю. Теперь (и окончательно) голуби сидят так: 0, 0, 0, 13, 9.

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

5
10 0 2 7 3
3

13 9

Задача 05. Треугольник ≡

Условие

Валерий Брюсов, "Треугольник", 1918 г.

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

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

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

1) В его первой строке единственная цифра 0.

2) Каждая следующая строка начинается с цифры, с которой начинается предыдущая строка, увеличенной на 1 и взятой по модулю 10 (то есть если предыдущая строка начинается с 9, то следующая начнётся с 0).

3) Каждая следующая цифра строки равна предыдущей цифре, увеличенной на 1 и взятой по модулю 10 (то есть если предыдущая цифра — 9, то следующая — 0).

4) В каждой новой строке на 2 цифры больше, чем в предыдущей.

На рисунке ниже вы можете видеть треугольник Тимофея с первыми 7 строками.

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

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

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

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

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

Выведите через пробел десять чисел — количество цифр от 0 до 9 в треугольнике.

Ограничения

1 ≤ n ≤ 10⁹

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

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

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

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

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

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

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

7

4 4 5 5 5 6 6 5 5 4

Задача 06. На абордаж! ≡

Условие

...

Первый подъезд,

Пятый этаж,

Нас затопляет —

На абордаж!

...

Генрих Сапгир, "Песня бабушки на крыше", 1970 г.

Песня из фильма "Приключения жёлтого чемоданчика"

В многоэтажном доме, высотой h этажей, в каждом подъезде на каждом этаже по k квартир. В квартире номер n сегодня прорвало трубу и все квартиры, расположенные строго ниже неё, затопило. Сколько всего квартир (включая n) пострадало?

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

Три строки входного файла содержат три натуральных числа: h, k и n.

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

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

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

Ограничения

1 ≤ h, k ≤ 10⁵

1 ≤ n ≤ 10¹⁸

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

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

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

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

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

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

Смотри рисунок. В примере дан девятиэтажный дом, в каждом подъезде на каждом этаже по 3 квартиры. Несчастливая квартира № 13 расположена на пятом этаже, вода также зальёт квартиры с номерами 1, 4, 7 и 10 — всего пять квартир.

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

9
3
13

5

Задача 07. На седьмом этаже ≡

Условие

...

На седьмом этаже за семь часов счастья

Спасибо тебе, и знаешь теперь

Увидеть бы вновь тебя я точно

Знаю, что такое любовь.

...

Лера Массква, "7 этаж", 2005 г.

hrefhttps: /  / www.youtube.com / watch?v = StsuEQz87HQВидеоклип

Девушка Лера очень любит цифру 7, считая, что она приносит ей удачу. Недавно она, наконец, накопила денег на новое жильё. Но Лера хочет найти такой подходящий строящийся многоэтажный жилой дом, чтобы у её будущего гнёздышка выполнялись сразу три важных условия:

1) Номер подъезда, в котором будет расположена её квартира, должен быть седьмой;

2) Номер этажа должен быть седьмой;

3) Номер квартиры должен состоять из семи семёрок, то есть быть равным 7777777.

Все строящиеся дома имеют две характеристики: k — количество квартир на каждом этаже и h — высота дома в этажах. Все подходящие дома Лера упорядочила по возрастанию k. Укажите n-й по счету подходящий дом. Для определенности считайте, что все дома имеют по меньшей мере семь подъездов.

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

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

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

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

Ограничения

1 ≤ n ≤ 28493

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

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

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

В первом примере наименьшее подходящее k = 1 (по одной квартире на этаже). При высоте дома h = 1296295 в первых шести подъездах будет 6 × 1296295 = 7777770 квартир. Тогда квартира номер 7777777 окажется в нужном подъезде на нужном для Леры этаже.

Во втором примере следующее подходящее k = 2 (по две квартиры на этаже). При высоте дома h = 648147 в первых шести подъездах будет 6 × 648147 × 2 = 7777764 квартир. Тогда квартира номер 7777777 (и соседняя 7777778) окажется в требуемом расположении.

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

1

1 1296295

2

2 648147

Задача 08. Мерцание светил ≡

Условие

Среди миров, в мерцании светил

Одной Звезды я повторяю имя…

Не потому, чтоб я Её любил,

А потому, что я томлюсь с другими.

И если мне сомненье тяжело,

Я у Неё одной ищу ответа,

Не потому, что от Неё светло,

А потому, что с Ней не надо света.

Иннокентий Анненский, "Среди миров", 1909 г.

Видеоклип

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1000

3 ≤ len(s_i), len(c_i) ≤ 20

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

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

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

В примере приведены шесть звёзд, относящихся к трём созвездиям.

К созвездию Ориона относятся Бетельгейзе и Ригель, причем Бетельгейзе (0.50) тусклее Ригеля.

К созвездию Большого пса относятся Адара, Везен и Сириус, причем Везен (1.82) тусклее остальных.

К созвездию Лиры относится Вега (0.03).

Из трех самых тусклых в своих созвездиях звезд, самой яркой является Вега.

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

6
Betelgeuse Orionis 0.50
Adhara Canis_Majoris 1.50
Vega Lyrae 0.03
Rigel Orionis 0.13
Wezen Canis_Majoris 1.82
Sirius Canis_Majoris -1.46

Vega

Задача 09. Стремительные углы ≡

Условие

...

Я с детства не любил овал!

Я с детства угол рисовал!

Павел Коган, "Гроза", 1936 г.

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

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

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

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

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

Ограничения

3 ≤ n ≤ 10⁵

1 ≤ x_i ≤ 90

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

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

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

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

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

3
45
0
45

90

4
45
90
90
0

45

Задача 10. На чердаке ≡

Условие

По дому бродит привиденье.

Весь день шаги над головой.

На чердаке мелькают тени.

По дому бродит домовой.

...

Борис Пастернак, "Июль", 1956 г.

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

Привидение способно перемещаться в клетку, занятую препятствием или домовым, но тратит на это 2 секунды (на перемещение в свободную — 1 секунду).

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

Участники не могут выходить за пределы чердака. Кто быстрее доберётся до финиша?

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

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

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

Выведите через пробел победителя (Ghost (привидение) или Brownie (домовой)) и время, за которое он доберётся до финиша. Если оба существа достигнут цели одновременно, выведите одно слово Draw.

Ограничения

1 ≤ n, m ≤ 40

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

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

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

В первом примере чердак представляет собой узкую полоску шириной в одну клетку без препятствий. Привидение и домовой стартуют с крайней левой клетки. Чтобы добраться до крайней правой клетки, привидению понадобится 4 секунды (по 1 секунде на преодоление каждой клетки), домовой же добежит за 2 секунды.

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

В третьем примере оба героя способны добраться до финиша за 18 секунд (смотри рисунок).

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

1 5
.....

Brownie 2

3 14
.#...#...#...#
.#.#.#.#.#.#.#
...#...#...#..

Ghost 18

4 13
.####..#...#.
.####..#...#.
.####....#...
.......####..

Draw

Задача 11. Костры рябин ≡

Условие

...

Я календарь переверну

И снова третье сентября.

На фото я твое взгляну

И снова третье сентября.

Но почему?

...

Игорь Николаев, "Третье сентября", 1994 г.

Видеоклип

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

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

По данному числу определите, какое число расположено на плашке с этим числом с другой стороны?

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

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

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

Выведите одно натуральное число — ответ на вопрос задачи. Если на обороте плашки не должно быть никакого числа (на календаре автора задачи после 31-го числа последовательно появляются три надписи: "Месяц переставить", "Вращать медленно" и аббревиатура завода-изготовителя), выведите число -1.

Ограничения

1 ≤ n ≤ 31

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

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

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

3

20

16

-1

Задача 12. Рассеянная няня ≡

Условие

По бульвару няня шла,

Няня мальчика везла.

Мальчик в саночках сидел,

Мальчик с саночек слетел.

Видит няня — легче стало,

И быстрее зашагала.

...

Эдуард Успенский, "Рассеянная няня", 1973 г.

Няня с мальчиком Эдиком на санках вышли из дома и с некоторой постоянной скоростью отправились на базар. Через несколько метров мальчик вывалился из санок и со скоростью в k раз медленнее поплёлся назад домой. Няня же, наоборот, увеличила скорость в k раз, дошла до базара и, обнаружив отсутствие ребёнка, с той же скоростью двинулась домой, куда пришла одновременно с Эдиком. Зная расстояние от дома до базара s, определите, на каком расстоянии от дома произошёл инцидент.

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

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

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

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

Ограничения

1 ≤ s ≤ 10⁹

2 ≤ k ≤ 10

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

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

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

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

В примере дано: расстояние от дома до базара 1000 м, после падения Эдик отправился домой со скоростью в два раза медленнее, а няня пошла дальше со скоростью в два раза быстрее.

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

1000
2

400

Задача 13. Формула наших времён ≡

Условие

...

И цифры соединятся,

И пальцы

Вопьются в ладонь...

На что ни разделишь 13 —

Получится дробь...

И огонь!

Михаил Светлов, "Тринадцать", 1930 г.

Хорошо этим поэтам! Срифмовал себе пару строк, добавил пафоса и восклицательных знаков — глядишь, уже и в "Литературной газете" напечатали, и в МАССОЛИТ приняли, и в "Грибоедов" пускают. Удобно пристроился Амвросий! А если ты математик и всю жизнь разрабатываешь теорию чисел? Напечатают твою формулу на первой странице "Известий"? Ага, жди, Фока... Так и проживёшь всю жизнь в крохотной комнатке с общей кухней под укоризненным взглядом жены.

Ну, хоть небольшую задачку про бесконечные периодические дроби удалось в "Математический вестник" пристроить, главный редактор к тринадцатой годовщине Октября собирал всё, что связано с этим числом. Через недельку денежку в кассе выдадут, можно будет и в Торгсин супругу сводить, и в Варьете...

Определите наименьшее натуральное число, при делении которого на 13 в записи цифр результата встретится число n. На десятичный разделитель (если он образуется) не обращайте внимания.

Для определённости считайте, что если число делится на 13 нацело, то дробной части не образуется.

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁹

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

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

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

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

В первом примере дано n = 1930.

25113 = [19.30]76...

Во втором примере дано n = 61.

213 = 0.15384[61]53...

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

1930

251

61

2

Задача 14. Остров Невезения ≡

Условие

...

Вроде не бездельники, и могли бы жить.

Им бы понедельники взять и отменить!

...

Леонид Дербенёв, "Остров невезения", 1968 г.

Песня из фильма "Бриллиантовая рука"

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

Вам, как цензору единственной на острове газеты "Island of Good Luck", поручено важное и ответственное дело — не допустить появления запрещенного слова на страницах издания. Причем нужно искать не только само слово, но и места в тексте, где оно появляется на стыках слов. Формально инструкция звучит так: если 6 подряд идущих букв строки (независимо от их регистра и расположенных между ними не-букв и знаков препинания) образуют слово "monday" — вся строка подлежит цензурированию. В противном случае она может быть напечатана. Автоматизируйте этот процесс.

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

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

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

Выведите n строк. Если строка не содержит запрещенного контента — выведите слово OK. В противном случае выведите слово CENSORED.

Ограничения

1 ≤ n ≤ 100

Длина любой строки не превышает 250 символов.

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

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

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

10
Monday Begins on Saturday is a 1965 science fantasy novel by Soviet writers Boris and Arkady Strugatsky.
Cyber-Monday is a marketing term for e-commerce transactions after Thanksgiving in the United States.
He bought a diamond aye. 
There was a huge storm on Dayton's base.
Do you speak Russian? C'mon!!! 1) 'Da' - yes; 2) 'net' - no. Easy!
All draped in lush greenery, coast and hills likewise, Island of bad fortune in the ocean lies.
There live the savages, wretched human tribe, On the surface - terrible, yet they're good inside.
2 + 2 = 4
Today /\/\onday.
Have you decided on the Detective Contest?

CENSORED
CENSORED
CENSORED
CENSORED
CENSORED
OK
OK
OK
OK
OK

Задача 15. Совершенно случайно ≡

Условие

Мы не знали друг друга до этого лета,

Мы болтались по свету, земле и воде.

И совершенно случайно мы взяли билеты

На соседние кресла на большой высоте

И мое сердце остановилось,

Мое сердце замерло.

...

Александр Васильев, "Мое сердце", 2000 г.

Видеоклип

Монсерат Кабалье и Рикки Мартин купили билеты на один и тот же авиарейс. Расположение мест в салоне приведено на рисунке: в каждом ряду 4 кресла посередине и по 3 кресла по краям. По количеству рядов n мест для пассажиров определите вероятность того, что знаменитости полетят рядом.

Соседними будем считать только места в одном и том же ряду, не разделенные проходом. Например, для места 1D соседним будет только место 1E, а для места 1E — два места: 1D и 1F. Считайте, что все билеты на рейс проданы и каждое место достаётся пассажиру абсолютно случайным образом.

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

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

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

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

Ограничения

1 ≤ n ≤ 100

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

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

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

В примере салон содержит единственный ряд (10 кресел: ABC DEFG HJK).

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

1

7 45

Задача 16. Слово ≡

Условие

В оный день, когда над миром новым

Бог склонял лицо свое, тогда

Солнце останавливали словом,

Словом разрушали города.

...

А для низкой жизни были числа,

Как домашний, подъяремный скот,

Потому что все оттенки смысла

Умное число передает.

...

Николай Гумилёв, "Слово", 1921 г.

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁸

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

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

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

100111110101

done

Задача 17. Бедный дровосек ≡

Условие

Далеко в лесу огромном,

Возле синих рек,

Жил с детьми в избушке тёмной

Бедный дровосек.

...

Анна Ахматова, "Колыбельная", 1915 г.

Дровосек обладает силой s, которая позволяет ему срубить за один день s² деревьев. Однако, проработав целый день, он устаёт, и на следующий день срубит уже (s − 1)² деревьев, на третий — (s − 2)² и так далее: проработав d дней подряд, на d + 1-й день дровосек срубит (s − d)² деревьев.

Дольше s дней подряд он работать не может, однако дровосек может взять выходной (в этот день он не срубит ни одного дерева) и на следующий день снова срубить s² деревьев. Определите, за какое наименьшее число дней дровосек срубит не менее n деревьев?

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

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

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

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

Ограничения

1 ≤ s ≤ 10

1 ≤ n ≤ 10⁵

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

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

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

В примере дано s = 3 и n = 30. Дровосек может придерживаться следующего расписания:

В первый день он срубит 9 деревьев.

Во второй день он отдыхает (всего 9 деревьев).

В третий день он срубит 9 деревьев (всего 18 деревьев).

В четвёртый день он срубит 4 дерева (всего 22 дерева).

В пятый день он отдыхает (всего 22 дерева).

В шестой день он срубит 9 деревьев (всего 31 дерево).

Есть и другие подходящие расписания, но быстрее 6 дней ему не управиться.

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

3
30

6

Задача 18. Лев ≡

Условие

Когда бороться с собой устал

Покинутый Гумилёв,

Поехал в Африку он и стал

Охотиться там на львов.

За гордость женщины, чей каблук

Топтал берега Невы,

За холод встреч и позор разлук

Расплачиваются львы.

...

Дмитрий Быков, "Когда бороться с собой устал…", 1995 г.

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

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

На фотографии размером n × m, сделанной с вертолёта, расположено изображение пустого прямоугольника толщиной в один пиксель — решётки и одного льва, обозначаемых символами "#" (ASCII-код 35). Прямоугольник имеет длину и ширину не менее трех пикселей, а его стороны параллельны границам изображения. Фон рисунка заполнен символами "." (ASCII-код 46).

По предложенной фотографии определите, попал ли лев внутрь клетки.

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

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

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

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

Ограничения

3 ≤ n, m ≤ 100

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

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

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

7 8
........
.######.
.#....#.
.#.#..#.
.#....#.
.######.
........

In

3 3
###
###
###

In

7 8
........
.#####..
.#...#..
.#...#..
.#####..
........
...#....

Out

Задача 19. Лёд ≡

Условие

...

Все твои слёзы превращаю в лёд

Я спрячу сердце, его никто не найдёт

Не вижу смысла кончить этот эпизод

Я вижу выход, но не могу найти вход...

...

Василий Еремин, "Лёд", 2021 г.

У Вас есть ориентированный граф без петель на N вершинах, заданный матрицей смежности, где 1 — ребро есть, 0 — ребра нет. У Вас есть вершина, которая является выходом, и есть несколько вершин, которые являются входами (выход не может одновременно являться и входом). Определите, с какого входа надо начать, чтобы кратчайший путь от входа до выхода был минимально возможным.

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

В первой строке вводятся числа N, Q и finish — количество вершин, количество входов и вершина выхода. Во второй строке вводится Q чисел — вершины входов. В остальных N строках вводится матрица смежности.

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

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

Ограничения

2 ≤ N ≤ 100

1 ≤ Q ≤ N − 1

1 ≤ finish, start ≤ N

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

3 2 3 
2 1 
0 1 1 
1 0 1 
1 1 0

1

Задача 20. Смутный сон ≡

Условие

...

София

Я гнева вашего никак не растолкую.

Он в доме здесь живет, великая напасть!

Шел в комнату, попал в другую.

Фамусов

Попал или хотел попасть?

...

София

По смутном сне безделица тревожит;

Сказать вам сон: поймете вы тогда.

Фамусов

Что за история?

София

Вам рассказать?

Фамусов

Ну да.

...

Александр Грибоедов, "Горе от ума", 1824 г.

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

Бог сна Гипнос готовит для Антона очередное сновидение. Его цель — так переставить все n квартир, расположенных в доме Антона, чтобы ни одна из них не осталась на своём исходном месте. Сколько у него есть способов это сделать?

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

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

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

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

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

Ограничения

1 ≤ n ≤ 20

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

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

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

В примере дано n = 3. Существует шесть перестановок чисел от 1 до 3: 123, 132, 213, 231, 312, 321.

Из них Гипносу подходят только две: 231 и 312.

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

3

2

Задача 21. Бестолковые числа ≡

Условие

Как бестолковы числа эти,

Какой сумбур в календаре;

...

Фёдор Тютчев, "Как бестолковы числа эти…", 1872 г.

У григорианского календаря есть несколько недостатков, в числе которых — неодинаковая продолжительность месяцев (28, 29, 30, 31 день) и несогласованность номеров дней в месяце с днями недели. За последние два века родились десятки проектов календарной реформы, направленных на исправление этих проблем, но ни один из них так и не был окончательно принят.

Дизайнер Фёдор разрабатывает макет календаря на следующий год. Согласно техническому заданию, на поле для каждого месяца выделяется ровно 5 строк (недель) и 7 столбцов (дней недели, первый — понедельник). При этом, возможно, возникнут следующие коллизии:

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

2) Месяц заканчивается не в воскресенье (кроме случая, описанного в пункте 3). Аналогично, в последней неделе этого месяца появляются бестолковые числа следующего месяца.

3) Месяц захватывает шесть календарных недель. В этом случае числа с шестой недели печатаются на пятой в те же дни недели через черту, например, 24/31. Бестолковые числа в конце месяца не печатаются.

4) Февраль невисокосного года заканчивается в воскресенье. Вся пятая неделя состоит из бестолковых первых чисел марта.

По описанию года определите, сколько бестолковых чисел придётся напечатать Фёдору.

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

Первая строка входного файла содержит две строчные английские буквы из набора (mo, tu, we, th, fr, sa, su) — день недели (перечислены по порядку от понедельника до воскресенья), на который приходится первое января. Во второй строке записано одно из двух слов: leap (високосный) или common (невисокосный) — тип года.

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

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

Ограничения

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

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

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

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

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

В январе (точнее, в поле для этого месяца) таких дней 5 (в начале месяца).

В феврале 1 в начале и 6 в конце.

В марте 1 в начале и 3 в конце.

В апреле 4 в начале и 1 в конце.

В мае 6 в начале.

В июне 2 в начале и 3 в конце.

В июле 4 в начале.

В августе 4 в конце.

В сентябре 3 в начале и 2 в конце.

В октябре 5 в начале.

В ноябре 1 в начале и 4 в конце.

В декабре 3 в начале и 1 в конце.

Всего 59 бестолковых чисел.

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

sa
common

59

Задача 22. Белая лебедь ≡

Условие

Средь чисел всех милей мне цифра — два.

То — лебедь белая средь тёмных знаков,

Цветок поникший средь поникших злаков,

На длинном теле сфинкса голова.

...

Людмила Вилькина, "Цифра 2", 1907 г.

Девочка Люда очень любит цифру 2 и всегда радуется, когда встречает число, все цифры которого — двойки. После того, как она узнала о существовании позиционных систем счисления с натуральными основаниями, отличными от традиционной десятичной, то вдруг поняла, что поводов для радости стало еще больше — ведь теперь можно порадоваться и при виде чисел 8, 62 или 8738 — они представляются в некоторых системах счисления в виде записи, состоящей из одних двоек! Действительно, 8 = 22₃, 62 = 222₅, 8738 = 2222₁₆. Все числа, представимые подобным образом, Люда называет лебедиными.

Особенную радость Люде теперь приносят числа, которые являются лебедиными сразу в нескольких позиционных системах счисления с натуральными основаниями. По данному числу, определите, принесет ли оно Людмиле особенную радость.

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

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

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

Выведете Yes, если это число можно представить в виде лебединого хотя бы в двух позиционных системах счисления с натуральными основаниями. Выведете No в противном случае.

Ограничения

1 ≤ n ≤ 10⁹

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

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

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

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

В первом примере дано n = 26 = 222₃ = 22₁₂.

Во втором примере дано n = 5. Это число не удастся представить в виде лебединого ни в одной позиционной системе счисления.

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

26

Yes

5

No

Задача 23. А над городом плывут облака ≡

Условие

Белый снег, серый лед, на растрескавшейся земле.

Одеялом лоскутным на ней — город в дорожной петле.

А над городом плывут облака, закрывая небесный свет.

А над городом — желтый дым, городу две тысячи лет,

Прожитых под светом Звезды по имени Солнце...

...

Виктор Цой, "Звезда по имени Солнце", 1987 г.

Видеоклип

Для моделирования прогноза погоды восьмиклассник Виктор разработал следующую систему, заданную на координатной плоскости. Ось абсцисс представляет собой поверхность земли, в каждой точке с целочисленными координатами которой находится жилой дом. В точке (0, s) расположено Солнце — точечный источник света. Ниже него расположены облака, заданные в виде отрезков, параллельных земле, и не пропускающих солнечный свет. Витю интересует, сколько домов сейчас находятся в тени.

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

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

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

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

Ограничения

1 ≤ h_i < s ≤ 1000

1 ≤ n ≤ 100

 − 1000 ≤ a_i < b_i ≤ 1000

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

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

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

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

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

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

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

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

7 2
1 -5 -3
3 -1 3

9

Задача 24. И на Марсе будут яблони цвести! ≡

Условие

Жить и верить — это замечательно!

Перед нами небывалые пути.

Утверждают космонавты и мечтатели,

Что на Марсе будут яблони цвести!

...

Евгений Долматовский, "И на Марсе будут яблони цвести", 1963 г.

hrefhttps: /  / www.youtube.com / watch?v = x5DR7v04YnEВидеоклип

Женя Славин — первый человек, родившийся на Марсе. Он еще маленький, и очень любит смотреть на электронные часы, висящие напротив его кровати. Больше всего ему нравятся моменты, когда все цифры на табло становятся одинаковыми. В такие моменты он всегда радуется и хлопает в ладоши.

Поскольку период обращения Марса вокруг своей оси отличается от земного, марсианские колонисты определили, что:

 — в одних марсианских сутках будет ровно h марсианских часов;

 — в одном марсианском часе будет ровно m марсианских минут;

 — в одной марсианской минуте будет ровно s марсианских секунд.

Текущее время на Марсе — h_M часов, m_M минут и s_M секунд. Через сколько секунд Женя захлопает в ладоши? Время на марсианских электронных часах выводится с ведущими нулями во всех разрядах, лишние разряды не используются.

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

В первых трех строках входного файла содержатся три натуральных числа h, m и s — описание разбиения марсианских суток. В следующих трех строках расположены три неотрицательных целых числа h_M, m_M и s_M — текущее время.

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

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

Ограничения

0 ≤ h_M < h ≤ 10⁶

0 ≤ m_M < m ≤ 10⁶

0 ≤ s_M < s ≤ 10⁶

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

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

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

В первом примере марсианские сутки ничем не отличаются от земных (24 часа по 60 минут по 60 секунд). Сейчас 23 часа 50 минут ровно (на табло горят цифры 23:50:00). Через 10 минут (или 600 секунд) на табло во всех разрядах будут гореть одни нули.

Во втором примере марсианские сутки содержат 627 часов по 5 минут по 777 секунд. Сейчас 49 часов 3 минуты и 2 секунды (на табло горят цифры 049:3:002). Через 61 час 3 минуты и 109 секунд (или 239425 марсианских секунд) на табло во всех разрядах будут гореть одни единицы.

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

24
60
60
23
50
0

600

627
5
777
49
3
2

239425

Задача 25. Аптека, улица, фонарь ≡

Условие

Ночь, улица, фонарь, аптека,

Бессмысленный и тусклый свет.

Живи еще хоть четверть века  —

Всё будет так. Исхода нет.

...

Александр Блок, "Ночь, улица, фонарь, аптека…", 1912 г.

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

Представим улицу отрезком координатной оси, на которой самый левый дом имеет координату 0. Будем считать размер домов ничтожно малым по сравнению с протяженностью улицы и станем отмечать их точками на оси.

У фонаря есть параметр "яркость", выражающий, на каком расстоянии от фонаря светло. Например, при яркости, равной 10, фонарь, установленный в точке x = 25, будет освещать улицу на отрезке от 15 до 35, включая границы.

У аптеки есть параметр "удаленность", выражающий, на каком расстоянии домов от нее, люди, живущие в этих домах, будут её посещать. Например, при удаленности, равной 100, аптека, размещенная в точке x = 25, будет посещаться людьми, живущими в домах с координатами на отрезке от 0 до 125, включая границы (домов с отрицательными координатами нет).

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

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

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

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

Ограничения

1 ≤ n, a, b ≤ 10⁵

0 ≤ x_i, y_i ≤ 10⁹

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

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

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

В примере дано пять домов, яркость фонаря 15 и удаленность аптеки 20. Фонарь может быть установлен либо в точке 15, либо в точке 25, в обоих случаях освещено будет 4 дома. Аптеку можно расположить в точке 20, в этом случае посещать её смогут все жители города.

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

5 15 20
0 6
10 5
20 0
30 7
40 10

4 28

Задача 26. Манит карусель ≡

Условие

...

Манит, манит, манит карусель

В путешествие по замкнутому кругу.

Дарит, дарит, дарит карусель

То надежду, то досадную разлуку.

...

Регина Лисиц, "Карусель", 1996 г.

В детском парке открылся новый аттракцион "Карусель" на n мест. Согласно технике безопасности при её эксплуатации рассаживать детей можно только таким образом, чтобы центр тяжести всех катающихся совпадал с центром карусели и расстояния между ними по окружности были одинаковыми. Например, при n = 6 одновременно могут кататься 2, 3 или 6 ребят, а при n = 5 — только ровно 5. Другими словами, разрешается запустить карусель, если на ней размещено k детей, причём k — делитель n и k ≠ 1.

В очереди к карусели стоит d детей. Дети, которые покатались на карусели, уходят в поисках новых развлечений. Какое минимальное количество запусков аттракциона следует осуществить, чтобы все дети прокатились на карусели ровно по одному разу?

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

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

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

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

Ограничения

1 ≤ n, d ≤ 10⁵

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

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

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

В первом примере дано n = 16 и d = 14 (карусель на 16 мест, в очереди 14 детей). Достаточно 3 запуска карусели: в первый раз прокатятся 8 ребят, во второй — 4, в третий — 2.

Во втором примере дано n = 15 и d = 7. Всех детей прокатить не получится, так как согласно правилам разрешено катать только по 3, 5 или 15 ребят.

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

16
14

3

15
7

-1

Задача 27. За шахматами ≡

Условие

...

За шахматами... Усмешкой

Дразня коридорный глаз.

Ведь шахматные же пешки!

И кто-то играет в нас.

...

Марина Цветаева, "Поэма конца", 1924 г.

Марина Цветаева, Андрей Белый и Саша Чёрный коротают вечер за шахматной доской. В каждой партии играют двое, третий ждет своей очереди, чтобы занять место проигравшего. Победитель предыдущей партии в следующей играет белыми фигурами. После завершения n партий поэты серебряного века с удивлением обнаружили, что белые выигрывали ровно k партий подряд, а в следующей партии всегда побеждали черные.

Андрей Белый любит играть белыми фигурами, Саша Чёрный — черными, Марина Цветаева любит играть любым цветом. Определите количество партий, в которых оба противника играли своим любимым цветом. В самой первой партии встречались Белый (играл белыми) и Черный. Ни одна партия не завершилась вничью.

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁹

1 ≤ k ≤ 100

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

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

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

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

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

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

Было сыграно 4 партии, игравший белыми выигрывал 1 партию, следующую — проигрывал.

В первой партии Белый — Чёрный оба играют любимым цветом. Игравший белыми Андрей побеждает.

Во второй партии Белый — Цветаева оба играют любимым цветом. Игравший белыми Андрей проигрывает.

В третьей партии Цветаева — Черный оба играют любимым цветом. Игравшая белыми Марина побеждает.

В последней партии Цветаева — Белый только Марина играет любимым цветом. Итого 3 партии.

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

4
1

3

Задача 28. Казанова ≡

Условие

...

Зачем делать сложным

То, что проще простого?

Ты — моя женщина,

Я — твой мужчина.

Если надо причину

То это — причина.

...

Илья Кормильцев, "Казанова", 1986 г.

Видеоклип

Женские (F) и мужские (M) последователи Хофштадтера (да, именно так они и называются в математике) рекурсивно определяются следующим образом:

M(0) = 0.

F(0) = 1.

M(n) = n − F(M(n − 1)), n > 0.

F(n) = n − M(F(n − 1)), n > 0.

Определите значение указанной функции. И не делайте сложным то, что проще простого!

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

Единственная строка входного файла содержит запись вида Y(n), где Y — обозначение функции (F или M), а n — неотрицательное целое число, её аргумент.

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

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

Ограничения

0 ≤ n ≤ 10⁵

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

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

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

В примере нужно вычислить F(1).

F(1) = 1 − M(F(1 − 1)) = 1 − M(F(0)) = 1 − M(1). Требуется сначала вычислить M(1).

M(1) = 1 − F(M(1 − 1)) = 1 − F(M(0)) = 1 − F(0) = 1 − 1 = 0.

Тогда F(1) = 1 − M(1) = 1 − 0 = 1.

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

F(1)

1

Задача 29. Латынь ≡

Условие

Гибло наше просвещенье,

Смерть была невдалеке,

Вдруг, о, радость! Есть спасенье —

Во латинском языке.

Если ж нас латынь обманет,

Все же выигрыш и тут,

Что ослов у нас не станет —

Всюду asin’ы пойдут!

...

Пётр Ершов, "Поклонникам латыни", 1860 г.

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

Например, в латинском языке у имён существительных целых пять склонений.

К первому склонению относятся существительные женского рода, в именительном падеже единственного числа (далее везде в этой форме), оканчивающиеся на a.

Ко второму склонению относятся существительные мужского рода, оканчивающиеся на us, er и ir, а также среднего рода, оканчивающиеся на um.

К третьему склонению относятся существительные среднего рода, оканчивающиеся на e, al и ar.

К четвёртому склонению относятся существительные мужского рода, оканчивающиеся на us и среднего рода, оканчивающиеся на u.

К пятому склонению относятся существительные женского рода, оканчивающиеся на es.

Это далеко не все правила определения рода слова, да и из приведённых есть огромное количество исключений (например, poeta — поэт, относится к первому склонению, но имеет мужской род, как и dies — день, относящийся к пятому склонению). Так что, если Вы хотите стать юристом, врачом, провизором, дипломатом или зоологом — сто раз подумайте, прежде чем подавать документы в соответствующий ВУЗ.

А прямо сейчас напишите простую программу.

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

Единственная строка входного файла содержит одно латинское слово, не относящееся к группе исключений из правил.

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

Выведите род приведённого слова — одно из трёх слов: masculinum (мужской род), femininum (женский) или neutrum (средний).

Ограничения

Длина слова не превышает 20.

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

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

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

Asinus (осёл) — второе склонение, мужской род. Asina (ослица) — первое склонение, женский род.

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

asinus

masculinum

asina

femininum

Задача 30. Дайте Оскар! ≡

Условие

...

Я как Федерико Феллини!

Дайте Оскар этой Богине

Словно кукла Барби на витрине

Хочет главную роль в картине

Будь моей, моей, моей!

И нам светят тысячи огней

И получим мы свой Оскар

Улетим за семь морей

(За семь морей, давай)

...

Евгений Трухин, "Федерико Феллини", 2021 г.

Видеоклип

Вот и определился шорт-лист номинанток на получение престижной премии Оскар за лучшую женскую роль. Согласно правилам, n членов актёрской гильдии сделали свой выбор, проголосовав за одну из пяти претенденток. Затем эти голоса считает одна из самых известных аудиторских компаний — PwC. Руководители процесса подсчёта голосов от PwC первыми узнают имена лауреатов «Оскара» ещё до того, как они будут объявлены на церемонии. Подсчет идет вручную, в засекреченном месте, известном лишь небольшой группе специалистов компании. И вот наконец Евгению, ответственному секретарю PwC, переслали результаты подсчета для печати карточки с именем обладательницы премии.

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

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

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

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

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

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

Ограничения

6 ≤ n ≤ 10⁹

11112 ≤ n ≤ 10⁵⁰

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

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

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

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

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

Во втором примере голоса распределились так: 123 8 57 10 102. Сумма всех чисел равна 300, других способов нет.

В третьем примере голоса могут распределиться так: 2 30 4 43 2. А могут и так: 2 30 44 3 2. Сумма в обоих случаях равна 81. Победить может как третья актриса, так и четвёртая.

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

6
12111

2

300
12385710102

1

81
2304432

-1

Задача 31. Пиф-Паф! ≡

Условие

Раз, два, три, четыре, пять,

Вышел зайчик погулять;

Вдруг охотник прибегает

Из ружья в него стреляет..,

Пиф-Паф! Ой-ой-ой!

Умирает зайчик мой!

Фёдор Миллер, "Раз, два, три, четыре, пять...", 1851 г.

На координатной прямой притаились три охотника. Каждый из них обладает своей зоной обзора и способен обнаружить зайца, если тот находится на прямой в пределах некоторого непрерывного отрезка, включая границы. Эти отрезки могут вырождаться в точки (охотник смотрит себе под ноги) и пересекаться или даже совпадать для различных охотников. Зайчик обладает параметром "ловкость", которая может принимать значение от 0 до 2. Если количество охотников, заметивших зверька, превысит ловкость зайца, они его подстрелят. По входным данным определите количество опасных для зайца точек координатной прямой с целыми координатами.

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

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

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

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

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

Ограничения

 − 10¹⁵ ≤ l_i, r_i ≤ 10¹⁵

0 ≤ a ≤ 2

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

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

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

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

Смотри верхний рисунок для 1-3 примеров, нижний — для 4-го примера.

В первом примере для зайца опасными являются точки с координатами от 0 до 11.

Во втором первом примере для зайца опасными являются точки с координатами от 2 до 10.

В третьем первом примере для зайца опасными являются точки с координатами от 4 до 7.

В четвёртом примере для зайца опасна единственная точка 4.

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

0 7
2 11
4 10
0

12

0 7
2 11
4 10
1

9

0 7
2 11
4 10
2

4

0 7
8 9
4 4
1

1

Задача 32. Часы стоят ≡

Условие

Часы остановились. Движенья больше нет.

Стоит, не разгораясь, за окнами рассвет.

...

И вечности безглазой беззвучен строй и лад.

Остановилось время. Часы, часы стоят!

Зинаида Гиппиус "Часы стоят", 1902 г.

После замены батарейки в электронных часах, Зинаиде требуется установить на индикаторе верное время. Для этого ей следует воспользоваться тремя кнопками, каждая из которых должна увеличивать число часов, минут и секунд на 1 соответственно. Однако, в последнее время эти кнопки барахлят — соответствующее число действительно увеличиваются на 1, зато два других на 1 уменьшаются! Например, если сейчас на индикаторе 12:34:56, то при нажатии на вторую кнопку время изменится на 11:35:55. Определите, какое минимальное количество нажатий на кнопки придётся сделать, чтобы установить нужное время.

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

Две строки входного файла содержат текущее и требуемое состояние индикатора в формате: hh:mm:ss с ведущими нулями. Гарантируется, что эти два момента времени различны.

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

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

Ограничения

00 ≤ hh ≤ 23

00 ≤ mm, ss ≤ 59

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

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

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

Сейчас на индикаторе 00:00:00. Зинаида дважды нажмёт на вторую кнопку (время изменится сперва на 23:01:59, затем на 22:02:58) и один раз на третью.

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

00:00:00
21:01:59

3

Задача 33. Табун ≡

Условие

...

От вершин скользя к вершинам,

Ветр ползет лесною высью.

Слышишь ржанье по долинам?

То табун несется рысью.

Афанасий Фет, "Летний вечер тих и ясен", 1847 г.

Однажды черный шахматный король, живущий на доске размером n × m, решил собрать большой табун белоснежных коней. Король для себя и коней может выбрать любые поля на доске. Конечно, ни один белый конь не должен атаковать черного короля. Какое минимальное количество пустых полей окажется на доске?

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

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

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

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

Ограничения

1 ≤ n, m ≤ 10

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

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

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

В примере на доске размером 2 × 4 какое бы место для себя не выбрал король, более 6 коней разместить нельзя. Одно поле останется пустым.

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

2 4

1

Задача 34. Дважды два ≡

Условие

...

Говорят, что где-то есть острова,

Где четыре на всегда дважды два,

Считай хоть дослепу — одна испарина,

Лишь то, что по сердцу, лишь то и правильно.

Вот какие есть на свете острова!

...

Александр Галич, "Песня про острова", 1966 г.

На одном из Тихоокеанских островов принято решение о внесении ровно одного изменения в таблицу умножения. Согласно новому правилу, теперь при умножении цифры a на цифру b (и наоборот) получается ровно n. По предложенному произведению двух многозначных чисел определите эти цифры и их новый результат умножения.

Считайте, что 1 ≤ a, b ≤ 9 и 0 ≤ n ≤ 99.

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

Три строки входного файла содержат два натуральных и одно целое неотрицательное числа: x, y и p. Первые два числа — множители, третье — их произведение, вычисленное по новым правилам. Гарантируется, что x × y ≠ p при обычном вычислении.

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

Выведите в трёх строках в том же формате три натуральных числа a, b и n — изменение в таблице умножения. Гарантируется, что во всех тестах такое изменение определяется единственным образом (в общем случае это не так). Числа a и b выведите в порядке не убывания.

Ограничения

10 ≤ x, y ≤ 10⁹

0 ≤ p ≤ 10¹⁸

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

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

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

В примере в таблицу умножения было внесено изменение 3 × 4 = 15. Смотри рисунок: слева умножение по обычным правилам, справа — по новым. Красным цветом выделены изменившиеся цифры.

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

234
43
10365

3
4
15

Задача 35. Снежный человек ≡

Условие

Говорят, что в Гималаях где-то,

Выше храмов и монастырей,

Он живет, неведомый для света,

Первобытный выкормыш зверей.

Безмятежный, белый и косматый,

Он порой спускается с высот,

И танцует, словно бесноватый,

И в снежки играет у ворот.

...

Николай Заболоцкий, "Снежный человек", 1957 г.

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

Первую кучку Йети складывает так: нижний слой снежков в форме квадрата со стороной k, на него — слой снарядов со стороной k − 1, и так далее. На самом верху лежит один снежок.

Вторую кучку Снежный человек складывает так: нижний слой снежков в форме правильного треугольника со стороной t, на него — слой снарядов со стороной t − 1, и так далее. На самом верху, опять-таки лежит один снежок.

На рисунке ниже Вы можете видеть первую кучку высотой 4 слоя (в ней 16 + 9 + 4 + 1 = 30 снежков) и вторую кучку высотой 5 слоёв (в ней 15 + 10 + 6 + 3 + 1 = 35 снежков).

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁵

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

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

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

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

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

В первом примере дано n = 3. Разложить на две кучки невозможно.

Второй пример разобран в условии задачи.

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

3

No

65

Yes

Задача 36. Конфеты ≡

Условие

Если друг на день рожденья,

Пригласил тебя к себе,

Ты оставь подарок дома —

Пригодится самому.

Сесть старайся рядом с тортом.

В разговоры не вступай.

Ты во время разговора

Вдвое меньше съешь конфет.

 ⋯ 

Григорий Остер, "Вредные советы", 1990 г.

Сегодня у Гриши день рождения! Каждый из его n друзей принёс имениннику в подарок коробку любимых конфет. Поскольку Гриша — мальчик не жадный, то все конфеты он вынул из коробок и разложил по n + 1 тарелочкам и поставил их перед каждым гостем (включая себя). Ко всеобщему восторгу, это удалось сделать без остатка. Сразу же после этого с работы вернулась мама и было решено все конфеты разложить уже по n + 2 тарелочкам. Ко всеобщему удивлению, и это деление удалось совершить без остатка.

По известному количеству конфет в одной коробке k, определите возможное число гостей на празднике.

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

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

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

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

Ограничения

1 ≤ k ≤ 10⁹

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

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

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

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

В примере число конфет в одной коробке равно 6.

Если к Грише пришел один гость, то общее число конфет тоже равно 6. Их несложно разложить без остатка поровну и по двум, и по трем тарелочкам.

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

Других подходящих решений нет.

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

6

2
1 2

Задача 37. Все флаги в гости будут к нам ≡

Условие

...

Природой здесь нам суждено

В Европу прорубить окно,

Ногою твердой стать при море.

Сюда по новым им волнам

Все флаги в гости будут к нам,

И запируем на просторе.

...

Александр Пушкин, "Медный всадник", 1833 г.

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

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

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

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

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

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

Выведите "Green", "White", "Red", "Yellow" или "Blue" (без кавычек) — ответ на вопрос задачи.

Ограничения

1 ≤ x, y ≤ 10⁹

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

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

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

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

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

10 10

Yellow

Задача 38. Разность ≡

Условие

...

В безмерной разности теряться

И благодарны слезы лить.

Гавриил Державин, "Бог", 1784 г.

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

На доске записано числовое выражение n − (n − 1) − (n − 2) − (n − 3) − ...  − 3 − 2 − 1 (например, при n = 5 будет написано 5 − 4 − 3 − 2 − 1). Чтобы избежать двойки, Гавриле требуется поставить в этом выражении левую и правую скобки, так, чтобы в результате получился ноль. Сколько у него есть способов это сделать?

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

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

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

Выведите в первой строке неотрицательное целое число m — количество способов расставить скобки требуемым образом. В следующих m строках через пробел выведите два натуральных числа a и b — положение скобок (числа от a до b включительно окажутся внутри скобок). Числа a и b выводите в порядке убывания, а пары чисел выводите в порядке убывания a.

Ограничения

4 ≤ n ≤ 10⁵

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

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

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

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

Во втором примере дано n = 7. Если все числа от 5 до 3 заключить в скобки, то получится выражение с нужным значением: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.

В третьем примере для n = 12 есть несколько способов решить задачу и продолжить обучение.

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

5

0

7

1
5 3

12

2
11 8
8 2

Задача 39. Странная улица ≡

Условие

Раз возвращаюсь домой я к себе,

Улица странною кажется мне.

Левая, правая где сторона?

Улица, улица, ты, брат, пьяна!

...

Василий Сиротин, "Улица", 1859 г.

Видеоклип

Студент Василий, вернувшись в родную деревню на каникулы, с размахом отмечает успешно сданную сессию. Он гуляет по единственной улице, схема которой приведена на рисунке. На этой улице a домов (с номерами 1, 3, 5, ..., a × 2 − 1) на левой и b домов (с номерами 2, 4, 6, ..., b × 2) на правой стороне. Посередине улицы разлилась огромная лужа, поэтому перейти с одной стороны на другую можно только в начале и в конце улицы.

Находясь около очередного дома, Василий случайным образом решает, куда ему идти дальше (каждое из двух возможных направлений он выбирает с вероятностью 12). Если он окажется рядом с трактиром (дом номер t), то непременно зайдет в него и продолжит веселиться до утра, а если окажется рядом со своим жилищем (дом номер h), то решит, что это знак судьбы и ему пора заканчивать развлекаться. Какова вероятность того, что Василий доберется до родного дома и завершит свой праздник, если сейчас он стоит около дома с номером n?

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

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

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

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

Ограничения

1 ≤ a, b ≤ 10⁹

1 ≤ t ≤ a × 2 − 1, если t — нечётное.

2 ≤ t ≤ b × 2, если t — чётное.

Для h и n ограничения аналогичны t.

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

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

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

Смотри рисунок. В примере на улице всего три дома (с номерами 1, 2 и 3). На левой стороне дома под номерами 1 и 3, на правой только 2. От каждого дома можно пройти к любому другому. Василий с равной вероятностью 12 может попасть как домой, так и в трактир.

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

2 1
1 2 3

1 2

Задача 40. Флажок ≡

Условие

Посмотрите, посмотрите!

Вот какой флажок у Мити!

Кто флажок подарил?

Митя сам смастерил!

...

Ольга Высотская, "Флажок", 1960 г.

Будем называть флажком пятиугольник, вершины которого — вершины некоторого квадрата и его центр.

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

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

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

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

Выведите в том же формате координаты пятой вершины.

Ограничения

 − 10⁸ ≤ x_i, y_i ≤ 10⁸

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

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

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

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

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

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

0 0
-1 3
-3 -1
1 -3

3 1

Задача 41. Колечко ≡

Условие

...

Колечко, колечко, кольцо,

Давно это было, давно.

Зачем я колечко дарил,

Сердечко твоё бередил?

Александр Шаганов, "Колечко", 1996 г.

Видеоклип

Одной из самых популярных дворовых игр детства автора этой задачи была "Колечко-колечко". Играли в неё так:

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

Ведущий по очереди обходит всех игроков, вкладывая им в «лодочку» свою, и произнося считалку: «Я ношу-ношу колечко и кому-то подарю». Водящий, вкладывая свои руки в руки участников, должен передать колечко любому из игроков так, чтобы остальные не догадались — кому именно.

Игрок, получивший «колечко», не должен подавать виду, что он его получил, а должен стараться сидеть с максимально невозмутимым лицом.

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

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

На крылечке n ребят играют в "Колечко". Начальная расстановка приведена на рисунке (игроки пронумерованы от 1 до n − 1, водящий — номер n). Спустя несколько минут расстановка была уже другой. Определите, какое наименьшее количество раз кольцо сменило владельца?

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

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

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

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

Ограничения

3 ≤ n ≤ 10⁵

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

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

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

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

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

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

5
3 1 2 5 4

5

Задача 42. Не выходи! ≡

Условие

Не выходи из комнаты, не совершай ошибку.

Зачем тебе Солнце, если ты куришь Шипку?

За дверью бессмысленно всё, особенно — возглас счастья.

Только в уборную — и сразу же возвращайся.

...

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

Что интересней на свете стены и стула?

Зачем выходить оттуда, куда вернешься вечером

таким же, каким ты был, тем более — изувеченным?

...

Не будь дураком! Будь тем, чем другие не были.

Не выходи из комнаты! То есть дай волю мебели,

слейся лицом с обоями. Запрись и забаррикадируйся

шкафом от хроноса, космоса, эроса, расы, вируса.

Иосиф Бродский, "Не выходи из комнаты…", 1970 г.

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

Многие люди испытывают стресс, взаимодействуя с окружающим миром, однако только у хикикомори это приводит к таким патологическим явлениям, как полная длительная самоизоляция. В некоторых случаях они годами могут не покидать своей квартиры или даже своей комнаты. По данным правительства Японии, на 2019 год в стране было 1,15 миллиона хикикомори в возрасте от 15 до 64 лет (около 1 % населения страны). Однако ввиду очевидных проблем с подсчётом установить точное число таких людей чрезвычайно трудно.

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

Студент-психолог Иосиф в рамках своей дипломной работы исследует проблему хикикомори. Обработав результаты наблюдений, опросов и тестов, он получил массив натуральных чисел, который теперь тщательно изучает.

Иосиф ввёл термин k-одинокое число. Это число, которое встречается в массиве в единственном экземпляре и отличается от любого другого числа в этом же списке не менее, чем на k. Например, в массиве из шести чисел [8, 2, 10, 8, 5, 1] есть:

1) четыре 1-одиноких числа — 1, 2, 5 и 10;

2) два 2-одиноких числа — 5 и 10;

3) одно 3-одинокое число — 5.

По данному массиву определите количество k-одиноких чисел в нём.

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

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

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

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

Ограничения

1 ≤ m, n ≤ 10⁵

1 ≤ x_i, y_i ≤ 10⁹

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

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

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

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

Пример разобран в условии задачи. Одиноких чисел со значениями k, превышающими 3, нет.

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

6
8 2 10 8 5 1
4
2 3 1 5

2
1
4
0

Задача 43. Свободный стих ≡

Условие

Сладкозвучная богиня,

Рифма золотая,

Слух чарует, стих созвучьем

Звонким замыкая.

И капризна, и лукава,

Вечно убегает.

Гений сам порой не сразу

Резвую поймает.

...

Фёдор Сологуб, "Рифма", 1880 г.

Катрен — четверостишие, рифмованная строфа в четыре строки. Схем рифмовки у катрена три: попарная aabb, перекрестная abab и опоясывающая abba.

Терцет — трёхстишие, строфа из трех строк. Схема рифмовки у терцета одна: aaa или bbb (все строки имеют одну рифму).

Вдохновлённый визитом музы, начинающий поэт Фёдор написал n строк с рифмами двух типов: a и b. Теперь ему необходимо оформить их в строфы вида катрен и терцет. Фёдор не согласен менять свои строки местами, но не возражает против замены строки с рифмы a на рифму b и наоборот. Какое наименьшее количество замен ему необходимо будет сделать, чтобы справиться с задачей? Каждая строфа должна иметь длину 3 или 4 и соответствовать одной из схем рифмовки.

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

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

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

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

Ограничения

6 ≤ n ≤ 10⁵

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

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

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

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

В примере дано n = 14 (Фёдор написал 14 строк, которые описываются рифмами ababbabbababaa). Этот набор необходимо разбить на части, каждая из которых может быть одного из 5 видов: aabb, abab, abba, aaa, bbb, сделав как можно меньше замен в исходной строке.

Это можно сделать всего с тремя заменами, получив, например, строку ababbbbbbbabab. Теперь строку можно разбить на подстроки разрешённого типа: abab bbb bbb abab. Меньшим количеством замен обойтись не получится.

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

14
ababbabbababaa

3

Задача 44. Сон землемера ≡

Условие

...

О Землемер, во сне усталом

Ты видишь тот далекий скат,

Где треугольник острым жалом

Впился в очерченный квадрат.

...

Эдуард Багрицкий, "Нарушение гармонии", 1915 г.

Уставшему за день землемеру Эдуарду снится геометрический сон: ему требуется внутри квадрата со стороной a разместить треугольник площадью S. При этом первая из вершин треугольника должна совпадать с левой нижней вершиной квадрата, а две другие — располагаться так: вторая — на верхней, а третья — на правой сторонах квадрата (возможно, включая его вершины).

Пусть b — неотрицательное целое число, выражающее расстояние от левой верхней вершины квадрата до второй вершины треугольника (0 ≤ b ≤ a).

Пусть c — неотрицательное целое число, выражающее расстояние от правой верхней вершины квадрата до третьей вершины треугольника (0 ≤ c ≤ a).

Определите количество различных пар b и c, удовлетворяющих поставленным условиям.

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

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

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

В первой строке выведите одно неотрицательное целое число n — количество подходящих пар. В следующих n строках выведите значения b и c — описание очередной пары. Пары следует упорядочить по возрастанию b, а если b совпадают, то по возрастанию c.

Входные данные таковы, что количество строк в ответе не превысит 100.

Ограничения

2 ≤ a ≤ 10⁶

1 ≤ S ≤ a²2

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

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

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

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

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

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

6
16

3
1 2
2 4
4 5

Задача 45. О нулях ≡

Условие

...

О вы, нули мои и нолики,

Я вас любил, я вас люблю!

Скорей лечитесь, меланхолики,

Прикосновением к нулю!

...

Николай Олейников, "О нулях", 1934 г.

Коля придумал новую функцию f(n, k), которую назвал обнуление числа. Она возвращает наименьшее количество цифр некоторого натурального числа n, при обнулении которых сумма цифр числа станет равна k. Например при n = 1025 и k = 6 значение функции равно 1 — достаточно в исходном числе обнулить всего одну цифру и получить число 1005.

При обнулении нельзя менять первую цифру исходного числа (ведущие нули выглядят некрасиво), поэтому значение функции f(1025, 7) не определено — Коля может добиться нужной суммы лишь обнулением первой цифры, что запрещено. Аналогично, не определено значение функции f(1025, 9) — сумма цифр исходного числа меньше 9 и функции f(234, 1) — ни одна из цифр исходного числа не равна единице.

Помогите Коле для заданных n и k определить значение функции.

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

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

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

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

Ограничения

10 ≤ n ≤ 10¹⁰⁰

1 ≤ k ≤ 10⁹

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

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

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

В первом примере достаточно обнулить две цифры и получить число 120450 (или 123006).

Во втором примере обнулять цифры не нужно, их сумма уже равна 15.

В третьем примере все цифры числа четные. Получить нечетную сумму обнулением невозможно.

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

123456 12

2

1248 15

0

2486204004228 13

-1

Задача 46. Мы могли бы служить в разведке ≡

Условие

...

От Алтуфьево до Пражской

Лишь на первый взгляд далеко:

Мы везем московские тайны

По секретным веткам метро.

...

Илья Калинников, "Метро", 2000 г.

Видеоклип

Супер-шпион агент-007 прибыл в столицу России, чтобы собрать слухи о секретном перегоне на Серпуховско-Тимирязевской линии московского метро. Всего на этой ветке n станций (и, соответственно n − 1 перегон), которыми пользуются москвичи и гости столицы. Джеймс Бонд под видом простого туриста несколько раз проехал из конца в конец этой ветки и узнал продолжительность в минутах для каждого перегона — a_i. Подозрения подтвердились — отдельные отечественные чиновники высокого ранга тратили на перемещение из конца в конец линии существенно меньше времени — всего t минут. Завербованный агент Епифан сообщил дополнительные сведения: между двумя станциями вроде бы существует секретный перегон, перемещение по которому занимает всего k минут, но где он находится — государственная тайна, доступа к которой у него нет. Немного подумав, агент-007 определил все возможные места для секретного перегона.

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

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

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

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

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ a_i, k, t ≤ 10⁹

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

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

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

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

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

В первом примере дано 11 станций. Время перемещения по секретному перегону — 3 минуты, воспользовавшись которым, чиновники высокого ранга затратят на общий путь всего 15 минут. Смотри рисунок:

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

Во втором примере входные данные таковы, что секретный путь невозможен.

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

11 3 15
1 2 1 3 4 1 2 5 3 1

5
1 6
2 7
3 8
6 10
7 11

2 5 10
10

0

Задача 47. Шашки ≡

Условие

Ноздрёв вспыхнул и подошел к Чичикову так близко, что тот отступил шага два назад.

 —Я тебя заставлю играть! Это ничего, что ты смешал шашки, я помню все ходы. Мы их поставим опять так, как были.

Николай Гоголь, поэма "Мёртвые души", 1842 г.

Современные шашечные программы используют особый формат файлов (.pdn). В его основе лежит Portable Game Notation, набор правил для хранения шашечной позиции.

Клетки игрового поля обозначаются числами от 1 до 32, так, как указано на рисунке.

Запись позиции, возникшей при игре, в этом файле оформляется особым тегом FEN. Вот его формат:

1) Указывается один из символов W или B — цвет шашек игрока, которому нужно делать очередной ход (в рамках нашей задачи эта информация несущественна). Сразу после буквы идёт разделитель — символ : (ASCII код 58);

2) Указывается один из символов W или B — цвет шашек игрока, позиции которых будут перечисляться. Сразу после буквы через запятую перечисляются поля, занятые шашками. Дамки обозначаются символом K (King). В случае, когда шашки игрока занимают все клетки числового диапазона, он указывается своим началом и концом, разделёнными символом - (ASCII код 58). В конце идёт разделитель — символ :;

3) В таком же формате указываются клетки, на которых расположены шашки другого игрока.

По приведённым данным в формате FEN определите расстановку фигур на доске.

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

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

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

Выведите 8 строк по 8 символов — шашечную диаграмму. Белые поля обозначайте символом . (ASCII код 46), пустые черные — символом # (ASCII код 35), белые шашки — символом w, белые дамки — символом W, чёрные шашки — символом b, чёрные дамки — символом B.

Ограничения

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

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

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

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

B:W18,24,27,28,K10,K15:B12,16,20,K22,K25,K29

.#.#.#.#
#.#.#.#.
.#.W.#.b
#.#.W.b.
.#.w.#.b
#.B.#.w.
.B.#.w.w
B.#.#.#.

B:BK1-12:W21-32

.B.B.B.B
B.B.B.B.
.B.B.B.B
#.#.#.#.
.#.#.#.#
w.w.w.w.
.w.w.w.w
w.w.w.w.

Задача 48. Вымыслы ≡

Условие

Вырыты рвы,

Вымыты крысы...

Был бы ты злым,

Сытым бы. Лысым.

Борис Гринберг, "Вымыслы Ы", 2001 г.

Борис очень любит букву "Ы". Особенно ему нравится рисовать её в квадрате размером 3 × 3 клеточек так, как показано на рисунке слева. Недавно ему подарили станок для лазерной резки фанеры и кусок соответствующего материала размером h × w клеточек. Какое наибольшее количество букв "Ы" сможет вырезать Борис из этого куска?

Поскольку буква "Ы" — диграф, её части можно размещать как угодно, при этом их можно поворачивать на угол, кратный 90°, но нельзя отражать зеркально (одна сторона фанерного листа покрыта нужным лаком, а другая — нет).

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

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

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

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

Ограничения

2 ≤ h ≤ 3

1 ≤ w ≤ 100

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

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

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

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

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

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

3 7

2

Задача 49. Старики и домино ≡

Условие

...

В туфлях на гвоздиках, в тоненьком свитере...

Глупая, всё тебя мучит одно:

Как бы подружки твои не увидели

Да старики, что стучат в домино.

...

"И опять во дворе", 1961 г.

Видеоклип

...

А тебе шлют привет

Окна тихого дома

Да ещё старики,

Что всё так же стучат в домино.

...

«Я тебя подожду», 1962 г.

Видеоклип

...

Стучат давным-давно

Другие каблучки,

И лишь за домино

Всё те же старики.

...

"Прошло три года", 1966 г.

Видеоклип

Лев Ошанин, "Дворовой цикл".

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

Стандартный набор традиционного домино включает в себя 28 костяшек. Костяшка домино представляет собой прямоугольную плитку, длина которой вдвое больше ширины. Её лицевая сторона разделена линией на две квадратные части. Каждая часть содержит от нуля до шести точек. В полном наборе представлены все комбинации пар от 0 до наибольшего количества точек на каждой из половинок костяшки. Недавно старики узнали, что в специализированных наборах домино возможное количество точек может доходить до девяти, двенадцати, пятнадцати, восемнадцати или быть произвольным. Соответственно, играть таким комплектом сможет большее число участников.

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

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

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

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