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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

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

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

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

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

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

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

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

Ограничения

 − 1015 ≤ n, s ≤ 1015

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

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

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

Стандартный вход Стандартный выход
1
1
2
3

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ a ≤ 100

2 ≤ b ≤ 100

1 ≤ c ≤ 109

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2
3
11
1 2

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

...

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

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

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

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

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

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

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

Ограничения

3 ≤ n ≤ 108

1 ≤ n, hs, ns, hb, nb, a, b ≤ 109

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
10 1 3 2 4 5 20
45

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

...

Лера Массква, "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
1 1296295
2
2
2 648147

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

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

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

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

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

...

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ m < n ≤ 105

0 ≤ di ≤ 109

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

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

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

Решения, верно работающие при di ≤ 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.

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

Стандартный вход Стандартный выход
1
5
10 0 2 7 3
3
13 9

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Валерий Брюсов, "Треугольник", 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 ≤ 109

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
7
4 4 5 5 5 6 6 5 5 4

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

Пятый этаж,

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

На абордаж!

...

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

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

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

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

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

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

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

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

Ограничения

1 ≤ h, k ≤ 105

1 ≤ n ≤ 1018

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
9
3
13
5

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

Венедикт Ерофеев, поэма "Москва — Петушки", 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 электричка отправилась обратно в Москву, через час она будет всё ещё в пути.

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

Стандартный вход Стандартный выход
1
21:00
To Moscow

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

Видеоклип

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1000

3 ≤ len(si), len(ci) ≤ 20

 − 2.00 ≤ b ≤ 10.00

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
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. Стремительные углы

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

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

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

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

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

Ограничения

3 ≤ n ≤ 105

1 ≤ xi ≤ 90

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

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

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

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

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

Стандартный вход Стандартный выход
1
3
45
0
45
90
2
4
45
90
90
0
45

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

Автор:Антон Карабанов   Ограничение времени:5 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

Борис Пастернак, "Июль", 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
1 5
.....
Brownie 2
2
3 14
.#...#...#...#
.#.#.#.#.#.#.#
...#...#...#..
Ghost 18
3
4 13
.####..#...#.
.####..#...#.
.####....#...
.......####..
Draw

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

Но почему?

...

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

Видеоклип

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 31

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

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

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

Стандартный вход Стандартный выход
1
3
20
2
16
-1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

...

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

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

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

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

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

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

Ограничения

1 ≤ s ≤ 109

2 ≤ k ≤ 10

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
1000
2
400

Задача 13. Мы могли бы служить в разведке

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

От Алтуфьево до Пражской

Лишь на первый взгляд далеко:

Мы везем московские тайны

По секретным веткам метро.

...

Илья Калинников, "Метро", 2000 г.

Видеоклип

Супер-шпион агент-007 прибыл в столицу России, чтобы собрать слухи о секретном перегоне на Серпуховско-Тимирязевской линии московского метро. Всего на этой ветке n станций (и, соответственно n − 1 перегон), которыми пользуются москвичи и гости столицы. Джеймс Бонд под видом простого туриста несколько раз проехал из конца в конец этой ветки и узнал продолжительность в минутах для каждого перегона — ai. Подозрения подтвердились — отдельные отечественные чиновники высокого ранга тратили на перемещение из конца в конец линии существенно меньше времени — всего t минут. Завербованный агент Епифан сообщил дополнительные сведения: между двумя станциями вроде бы существует секретный перегон, перемещение по которому занимает всего k минут, но где он находится — государственная тайна, доступа к которой у него нет. Немного подумав, агент-007 определил все возможные места для секретного перегона.

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

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

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

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

Ограничения

2 ≤ n ≤ 105

1 ≤ ai, k, t ≤ 109

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

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

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

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

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

В первом примере дано 11 станций. Время перемещения по секретному перегону — 3 минуты, воспользовавшись которым, чиновники высокого ранга затратят на общий путь всего 15 минут. Смотри рисунок:

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

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

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

Стандартный вход Стандартный выход
1
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
2 5 10
10
0

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

...

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100

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

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

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

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

Стандартный вход Стандартный выход
1
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. Совершенно случайно

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

...

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

Видеоклип

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100

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

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

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

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

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

Стандартный вход Стандартный выход
1
1
7 45

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

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

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

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

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

...

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1018

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

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

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

Стандартный вход Стандартный выход
1
100111110101
done

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

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

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

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

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

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

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

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

Ограничения

1 ≤ s ≤ 10

1 ≤ n ≤ 105

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

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

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

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
3
30
6

Задача 18. Лев

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

...

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

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

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

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

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

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

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

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

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

Ограничения

3 ≤ n, m ≤ 100

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

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

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

Стандартный вход Стандартный выход
1
7 8
........
.######.
.#....#.
.#.#..#.
.#....#.
.######.
........
In
2
3 3
###
###
###
In
3
7 8
........
.#####..
.#...#..
.#...#..
.#####..
........
...#....
Out

Задача 19. Лёд

Автор:Евгений Татаринов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:128 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

...

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100

1 ≤ Q ≤ N − 1

1 ≤ finish, start ≤ N

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

Стандартный вход Стандартный выход
1
3 2 3 
2 1 
0 1 1 
1 0 1 
1 1 0
1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

София

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

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

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

Фамусов

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

...

София

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

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

Фамусов

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

София

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

Фамусов

Ну да.

...

Александр Грибоедов, "Горе от ума", 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.

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

Стандартный вход Стандартный выход
1
3
2

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

...

Фёдор Тютчев, "Как бестолковы числа эти…", 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 бестолковых чисел.

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

Стандартный вход Стандартный выход
1
sa
common
59

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 109

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

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

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

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

В первом примере дано n = 26 = 2223 = 2212.

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

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

Стандартный вход Стандартный выход
1
26
Yes
2
5
No

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

...

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

Видеоклип

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

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

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

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

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

Ограничения

1 ≤ hi < s ≤ 1000

1 ≤ n ≤ 100

 − 1000 ≤ ai < bi ≤ 1000

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
7 2
1 -5 -3
3 -1 3
9

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ hM < h ≤ 106

0 ≤ mM < m ≤ 106

0 ≤ sM < s ≤ 106

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
24
60
60
23
50
0
600
2
627
5
777
49
3
2
239425

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

...

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n, a, b ≤ 105

0 ≤ xi, yi ≤ 109

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

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

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

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

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

Стандартный вход Стандартный выход
1
5 15 20
0 6
10 5
20 0
30 7
40 10
4 28

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

...

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

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

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

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

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

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

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

Ограничения

1 ≤ n, d ≤ 105

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
16
14
3
2
15
7
-1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

...

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 109

1 ≤ k ≤ 100

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

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

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

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
4
1
3

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

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

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

...

Илья Кормильцев, "Казанова", 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 ≤ 105

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

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

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

В примере нужно вычислить 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.

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

Стандартный вход Стандартный выход
1
F(1)
1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
asinus
masculinum
2
asina
femininum

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

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

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

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

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

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

...

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

Видеоклип

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

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

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

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

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

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

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

Ограничения

6 ≤ n ≤ 109

11112 ≤ n ≤ 1050

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

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

Решения, верно работающие при 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. Победить может как третья актриса, так и четвёртая.

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

Стандартный вход Стандартный выход
1
6
12111
2
2
300
12385710102
1
3
81
2304432
-1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

 − 1015 ≤ li, ri ≤ 1015

0 ≤ a ≤ 2

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

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

Решения, верно работающие при  − 105 ≤ li, ri ≤ 105, получат не менее 50 баллов.

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
0 7
2 11
4 10
0
12
2
0 7
2 11
4 10
1
9
3
0 7
2 11
4 10
2
4
4
0 7
8 9
4 4
1
1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

...

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

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

Зинаида Гиппиус "Часы стоят", 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) и один раз на третью.

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

Стандартный вход Стандартный выход
1
00:00:00
21:01:59
3

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n, m ≤ 10

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

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

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

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

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

Стандартный вход Стандартный выход
1
2 4
1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

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

...

Александр Галич, "Песня про острова", 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 ≤ 109

0 ≤ p ≤ 1018

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

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

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

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

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

Стандартный вход Стандартный выход
1
234
43
10365
3
4
15

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

...

Николай Заболоцкий, "Снежный человек", 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 ≤ 1015

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
3
No
2
65
Yes

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ k ≤ 109

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
6
2
1 2

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

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

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

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

Все флаги в гости будут к нам,

И запируем на просторе.

...

Александр Пушкин, "Медный всадник", 1833 г.

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

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

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

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

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

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

Выведите "Green", "White", "Red", "Yellow" или "Blue" (без кавычек) — ответ на вопрос задачи.

Ограничения

1 ≤ x, y ≤ 109

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

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

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

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

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

Стандартный вход Стандартный выход
1
10 10
Yellow

Задача 38. Разность

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

В безмерной разности теряться

И благодарны слезы лить.

Гавриил Державин, "Бог", 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 ≤ 105

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

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

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

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

Во втором примере дано n = 7. Если все числа от 5 до 3 заключить в скобки, то получится выражение с нужным значением: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.

В третьем примере для n = 12 есть несколько способов решить задачу и продолжить обучение.

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

Стандартный вход Стандартный выход
1
5
0
2
7
1
5 3
3
12
2
11 8
8 2

Задача 39. Странная улица

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Раз возвращаюсь домой я к себе,

Улица странною кажется мне.

Левая, правая где сторона?

Улица, улица, ты, брат, пьяна!

...

Василий Сиротин, "Улица", 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 ≤ 109

1 ≤ t ≤ a × 2 − 1, если t — нечётное.

2 ≤ t ≤ b × 2, если t — чётное.

Для h и n ограничения аналогичны t.

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

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

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

Смотри рисунок. В примере на улице всего три дома (с номерами 1, 2 и 3). На левой стороне дома под номерами 1 и 3, на правой только 2. От каждого дома можно пройти к любому другому. Василий с равной вероятностью 12 может попасть как домой, так и в трактир.

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

Стандартный вход Стандартный выход
1
2 1
1 2 3
1 2

Задача 40. Флажок

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Посмотрите, посмотрите!

Вот какой флажок у Мити!

Кто флажок подарил?

Митя сам смастерил!

...

Ольга Высотская, "Флажок", 1960 г.

Будем называть флажком пятиугольник, вершины которого — вершины некоторого квадрата и его центр.

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

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

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

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

Выведите в том же формате координаты пятой вершины.

Ограничения

 − 108 ≤ xi, yi ≤ 108

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
0 0
-1 3
-3 -1
1 -3
3 1

Задача 41. Колечко

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

Колечко, колечко, кольцо,

Давно это было, давно.

Зачем я колечко дарил,

Сердечко твоё бередил?

Александр Шаганов, "Колечко", 1996 г.

Видеоклип

Одной из самых популярных дворовых игр детства автора этой задачи была "Колечко-колечко". Играли в неё так:

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

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

Игрок, получивший «колечко», не должен подавать виду, что он его получил, а должен стараться сидеть с максимально невозмутимым лицом.

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

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

На крылечке n ребят играют в "Колечко". Начальная расстановка приведена на рисунке (игроки пронумерованы от 1 до n − 1, водящий — номер n). Спустя несколько минут расстановка была уже другой. Определите, какое наименьшее количество раз кольцо сменило владельца?

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

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

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

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

Ограничения

3 ≤ n ≤ 105

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
5
3 1 2 5 4
5

Задача 42. Не выходи!

Автор:Антон Карабанов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Не выходи из комнаты, не совершай ошибку.

Зачем тебе Солнце, если ты куришь Шипку?

За дверью бессмысленно всё, особенно — возглас счастья.

Только в уборную — и сразу же возвращайся.

...

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

Что интересней на свете стены и стула?

Зачем выходить оттуда, куда вернешься вечером

таким же, каким ты был, тем более — изувеченным?

...

Не будь дураком! Будь тем, чем другие не были.

Не выходи из комнаты! То есть дай волю мебели,

слейся лицом с обоями. Запрись и забаррикадируйся

шкафом от хроноса, космоса, эроса, расы, вируса.

Иосиф Бродский, "Не выходи из комнаты…", 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 натуральных чисел xi — сами числа. В третьей строке содержится натуральное число m — количество запросов. В последней строке через пробел записаны m натуральных чисел ki — интересующие Иосифа значения k.

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

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

Ограничения

1 ≤ m, n ≤ 105

1 ≤ xi, yi ≤ 109

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

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

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

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

Пример разобран в условии задачи. Одиноких чисел со значениями k, превышающими 3, нет.

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

Стандартный вход Стандартный выход
1
6
8 2 10 8 5 1
4
2 3 1 5
2
1
4
0

Задача 43. Свободный стих

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Сладкозвучная богиня,

Рифма золотая,

Слух чарует, стих созвучьем

Звонким замыкая.

И капризна, и лукава,

Вечно убегает.

Гений сам порой не сразу

Резвую поймает.

...

Фёдор Сологуб, "Рифма", 1880 г.

Катрен — четверостишие, рифмованная строфа в четыре строки. Схем рифмовки у катрена три: попарная aabb, перекрестная abab и опоясывающая abba.

Терцет — трёхстишие, строфа из трех строк. Схема рифмовки у терцета одна: aaa или bbb (все строки имеют одну рифму).

Вдохновлённый визитом музы, начинающий поэт Фёдор написал n строк с рифмами двух типов: a и b. Теперь ему необходимо оформить их в строфы вида катрен и терцет. Фёдор не согласен менять свои строки местами, но не возражает против замены строки с рифмы a на рифму b и наоборот. Какое наименьшее количество замен ему необходимо будет сделать, чтобы справиться с задачей? Каждая строфа должна иметь длину 3 или 4 и соответствовать одной из схем рифмовки.

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

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

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

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

Ограничения

6 ≤ n ≤ 105

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

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

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

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

В примере дано n = 14 (Фёдор написал 14 строк, которые описываются рифмами ababbabbababaa). Этот набор необходимо разбить на части, каждая из которых может быть одного из 5 видов: aabb, abab, abba, aaa, bbb, сделав как можно меньше замен в исходной строке.

Это можно сделать всего с тремя заменами, получив, например, строку ababbbbbbbabab. Теперь строку можно разбить на подстроки разрешённого типа: abab bbb bbb abab. Меньшим количеством замен обойтись не получится.

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

Стандартный вход Стандартный выход
1
14
ababbabbababaa
3

Задача 44. Сон землемера

Автор:Антон Карабанов   Ограничение времени:0.3 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

О Землемер, во сне усталом

Ты видишь тот далекий скат,

Где треугольник острым жалом

Впился в очерченный квадрат.

...

Эдуард Багрицкий, "Нарушение гармонии", 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 ≤ 106

1 ≤ S ≤ a22

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
6
16
3
1 2
2 4
4 5

Задача 45. О нулях

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

О вы, нули мои и нолики,

Я вас любил, я вас люблю!

Скорей лечитесь, меланхолики,

Прикосновением к нулю!

...

Николай Олейников, "О нулях", 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 ≤ 10100

1 ≤ k ≤ 109

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

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

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

В первом примере достаточно обнулить две цифры и получить число 120450 (или 123006).

Во втором примере обнулять цифры не нужно, их сумма уже равна 15.

В третьем примере все цифры числа четные. Получить нечетную сумму обнулением невозможно.

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

Стандартный вход Стандартный выход
1
123456 12
2
2
1248 15
0
3
2486204004228 13
-1

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

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

И пальцы

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

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

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

И огонь!

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 109

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

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

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

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

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

25113 = [19.30]76...

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

213 = 0.15384[61]53...

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

Стандартный вход Стандартный выход
1
1930
251
2
61
2

Задача 47. Шашки

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Ноздрёв вспыхнул и подошел к Чичикову так близко, что тот отступил шага два назад.

 —Я тебя заставлю играть! Это ничего, что ты смешал шашки, я помню все ходы. Мы их поставим опять так, как были.

Николай Гоголь, поэма "Мёртвые души", 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.

Ограничения

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

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

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

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

Стандартный вход Стандартный выход
1
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.#.#.#.
2
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. Вымыслы

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Вырыты рвы,

Вымыты крысы...

Был бы ты злым,

Сытым бы. Лысым.

Борис Гринберг, "Вымыслы Ы", 2001 г.

Борис очень любит букву "Ы". Особенно ему нравится рисовать её в квадрате размером 3 × 3 клеточек так, как показано на рисунке слева. Недавно ему подарили станок для лазерной резки фанеры и кусок соответствующего материала размером h × w клеточек. Какое наибольшее количество букв "Ы" сможет вырезать Борис из этого куска?

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

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

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

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

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

Ограничения

2 ≤ h ≤ 3

1 ≤ w ≤ 100

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
3 7
2

Задача 49. Старики и домино

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

В туфлях на гвоздиках, в тоненьком свитере...

Глупая, всё тебя мучит одно:

Как бы подружки твои не увидели

Да старики, что стучат в домино.

...

"А у нас во дворе", 1961 г.

...

А тебе шлют привет

Окна тихого дома

Да ещё старики,

Что всё так же стучат в домино.

...

"И опять во дворе", 1962 г.

...

Стучат давным-давно

Другие каблучки,

И лишь за домино

Всё те же старики.

...

"Прошло три года", 1966 г.

Лев Ошанин, "Дворовой цикл".

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

Стандартный набор традиционного домино включает в себя 28 костяшек. Костяшка домино представляет собой прямоугольную плитку, длина которой вдвое больше ширины. Её лицевая сторона разделена линией на две квадратные части. Каждая часть содержит от нуля до шести точек. В полном наборе представлены все комбинации пар от 0 до наибольшего количества точек на каждой из половинок костяшки. Недавно старики узнали, что в специализированных наборах домино возможное количество точек может доходить до девяти, двенадцати, пятнадцати, восемнадцати или быть произвольным. Соответственно, играть таким комплектом сможет большее число участников.

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

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

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

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

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

Выведите одну десятичную цифру — ответ на вопрос задачи.

Ограничения

0 ≤ n ≤ 1018

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

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

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

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

В первом примере набор состоит из единственной костяшки "пусто-пусто". Сумма всех чисел равна 0.

Во втором примере в полном нестандартном наборе, если наибольшее число точек на одной части костяшки равно трём, будет 10 костяшек. Сумма всех чисел: 1 + 2 + 3 + 1 + 1 + 2 + 1 + 3 + 1 + 2 + 2 + 3 + 2 + 3 + 3 = 30. Последняя цифра — 0.

В третьем примере в стандартном наборе домино, наибольшее число точек на одной части костяшки равно шести. Полный набор составляет 28 костяшек. Сумма всех чисел равна 168. Последняя цифра — 8.

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

Стандартный вход Стандартный выход
1
0
0
2
3
0
3
6
8

Задача 50. Два города

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Я, как поезд, что мечется столько уж лет

Между городом Да и городом Нет.

Мои нервы натянуты, как провода,

Между городом Нет и городом Да!

...

Евгений Евтушенко "Два города", 1964 г.

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

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

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

Для каждого города выведите Yes или No. Очередной ответ выводите с новой строки.

Ограничения

1 ≤ n ≤ 1000

1 ≤ len(s) ≤ 100

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

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

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

Стандартный вход Стандартный выход
1
6
Yekaterinburg
Vladivostok
Novokuznetsk
Kaliningrad
Tyumen
Birobidzhan
No
Yes
No
Yes
No
Yes

Задача 51. Дядя Стёпа

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

Дядя Степа просит кассу:

 — Я пришел на карнавал.

Дайте мне такую маску,

Чтоб никто не узнавал!

 — Вас узнать довольно просто,  —

Раздается дружный смех,  —

Мы узнаем вас по росту:

Вы, товарищ, выше всех!

...

Сергей Михалков, "Дядя Стёпа", 1935 г.

Будем рассматривать имя "stepa" и маски, состоящие из маленьких английских букв и символов "?" и "*". Говорят, что слово подходит под маску, если в маске можно заменить каждый символ «?» на маленькую английскую букву, а каждый символ "*" — на последовательность (возможно, пустую) маленьких английских букв, так, чтобы получилось слово "stepa". Требуется написать программу, определяющую, подходит ли данная маска s имени.

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

Единственная строка входного файла содержит строку, состоящую из маленьких английских букв, а также символов "?" (ASCII код 63) и "*" (ASCII код 42). Гарантируется, что строка не содержит 2 и более подряд идущих символов "*".

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

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

Ограничения

1 ≤ len(s) ≤ 10

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

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

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

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

В первом примере под данную маску подходит любое имя.

Во втором примере можно заменить символы "?" на недостающие буквы имени.

В третьем примере можно заменить первый символ "*" на "st", второй символ "*" на пустую строку, а символ "?" на букву "a".

В четвертом примере никакие замены не позволят получить имя "stepa" — буквы "p" и "t" невозможно поменять местами.

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

Стандартный вход Стандартный выход
1
*
Yes
2
s??p?
Yes
3
*e*p?
Yes
4
*p*t*
No

Задача 52. Скоро дембель

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

На попутке приеду домой.

Эх, я вас зацелую в стороночке

И не знаю — в кого я такой.

Как я буду вас кверху подбрасывать,

Громко-громко о жизни кричать,

О медаль медалью позвякивать.

И о прошлом мне наплевать.

...

Михаил Андреев, "Скоро дембель", 1996 г.

Видеоклип

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

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

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

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

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

Ограничения

1 ≤ n ≤ 109

1 ≤ x < y ≤ n

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

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

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

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

В первом примере Михаилу нужно отслужить 12 дней. К сегодняшнему вечеру он отслужил 14 часть службы или 3 дня. Завтра он отслужит уже 4 дня, что составляет 13 часть службы.

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

Стандартный вход Стандартный выход
1
12
1 4
1 3
2
365
218 365
3 5
3
1000
999 1000
1 1

Задача 53. Две бабочки

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Две бабочки дневных в ночи немой

Вслепую бились в ожиданьи встречи,

Но был как будто ночью засекречен

Их путь друг к другу, днем такой прямой.

...

Георгий Васильев и Алексей Иващенко, "Две бабочки", 1981 г.

В теории графов граф «бабочка» (а также «галстук-бабочка» или «песочные часы») — это планарный неориентированный граф с 5 вершинами и 6 рёбрами (смотри рисунок).

Неориентированный граф задан матрицей смежности. Определите, можно ли в нём выделить хотя бы два подграфа «бабочка», не имеющих общих вершин?

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

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

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

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

Ограничения

10 ≤ n ≤ 30

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

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

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

Смотри рисунок. Два подграфа «бабочка» выделены красным и синим цветом.

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

Стандартный вход Стандартный выход
1
10
0100100000
1011100000
0100010001
0100011000
1100000110
0011001001
0001010010
0000100010
0000101101
0010010010
Yes

Задача 54. Многоугольник скул

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Пришла. Стоит. Ей восемнадцать лет.

 — Вам сколько лет?  — Ответила:  — Осьмнадцать. —

Многоугольник скул, локтей, колен.

Надменность, угловатость и косматость.

...

Белла Ахмадулина, "Пришла. Стоит. Ей восемнадцать лет...", 1974 г.

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

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

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

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

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

Ограничения

3 ≤ n ≤ 6

1 ≤ ai ≤ 108

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
6
4 1 3 3 2 2
35

Задача 55. Машина времени

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Попадись мне машина времени!

Я бы не к первобытному племени

полетел, на костров его дым,

а в страну, где не чувствуешь бремени

лет, где я бы стал молодым.

...

Борис Слуцкий, "Как использовать машину времени", 1959 г.

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

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

Хронологически путешествия во времени главного героя можно представить следующей схемой: после рождения он прожил a лет, переместился в недалёкое будущее на b лет вперёд, прожил там c лет, переместился в прошлое на d лет назад, прожил там e лет, переместился в далёкое будущее на f лет вперёд.

Автор написал уже много томов и постепенно стал сбиваться и путаться в датах и числах. В частности, ему постоянно требуется помнить, сколько полных лет прожил его герой к 1 января n-го года. Напишите программу, помогающую найти ответ на этот вопрос. Для определенности, считайте, что день рождения героя произведения 1 января 2000 года и все перемещения во времени происходили тоже только 1 января.

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

Семь строк входного файла содержат семь натуральных чисел: a, b, c, d, e, f и n.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи. Если главный герой не существовал в n-м году, выведите число -1.

Ограничения

1 ≤ a, b, c, d, e, f ≤ 1000

d > a + b + c

e < d − (a + b + c)

f > d − e

1000 ≤ n ≤ 3000

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

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

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

Все примеры из условия соответствуют схеме выше (в масштабе: 1 клетка равна 4 годам). В других тестах входные данные могут быть иными.

В первом примере требуется узнать, сколько лет прожил главный герой к 1 января 2000 года. Он только родился и прожил пока 0 лет.

Во втором примере 1 января 2023 года главный герой не существовал (он совершал своё первое путешествие).

В третьем примере к 1 января 1988 года главный герой прожил a + c + 8 лет  = 44 года.

В четвёртом примере к 1 января 1992 года главный герой прожил уже a + c + e = 48 лет (через пару минут он отправится в своё третье путешествие).

В пятом примере к 1 января 2052 года главный герой прожил те же a + c + e = 48 лет (пару минут назад он совершил своё третье путешествие).

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

Стандартный вход Стандартный выход
1
16
12
20
68
12
60
2000
0
2
16
12
20
68
12
60
2023
-1
3
16
12
20
68
12
60
1988
44
4
16
12
20
68
12
60
1992
48
5
16
12
20
68
12
60
2052
48

Задача 56. Гороскоп

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

Моя подруга родилась под знаком крысы —

Не оказалось в книге знака соловья.

По гороскопу мама тоже не актриса,

А папа вовсе получается — свинья.

...

И вот семья, обычная семья —

Мама, папа, я.

Живёт семья, приличная семья —

Лошадь, крыса и свинья.

...

Сергей Катин, "Гороскоп", 1991 г.

Видеоклип

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

10-летний цикл («небесные стволы»). Каждый из пяти элементов или стихий (металл, дерево, вода, огонь и земля) длится по два года:

12-летний цикл («земные ветви»). Характеристики зодиакальных животных (крыса, бык, тигр и т. д.) отличаются художественностью формы, а также богатством и психологической достоверностью содержания.

Например, 2022 год — год Водного Тигра. По данному номеру года n определите его описание по восточному гороскопу.

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

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

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

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

Первое слово из списка [Metal, Water, Wood, Fire, Earth].

Второе слово из списка [Rat, Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig].

Оба списка отсортированы в порядке "сменяемости".

Ограничения

2023 ≤ n ≤ 109

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

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

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

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

2022 год — год Водного Тигра. Следующий — тоже водный, год Кролика.

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

Стандартный вход Стандартный выход
1
2023
Water Rabbit

Задача 57. Славный праздник

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

Новый Год к нам мчится,

Скоро все случится,

Сбудется что снится,

Что опять нас обманут, ничего не дадут.

Ждать уже недолго,

Скоро будет елка.

Только мало толка,

Если Дед Мороза дети от беды не спасут.

...

Алексей Рыжов, "Новогодняя", 1999 г.

Видеоклип

Детский утренник проходил в полном соответствии со сценарием. Сказочные злодеи пустили по неверной дороге Снеговика, успешно похитили Снегурочку и лишили Деда Мороза мешка с подарками. Оставалось только разобраться с детьми (пятиклассниками Лицея программистов имени Фортрана), но, нашла коса на камень! Дети успешно закидали снежками Бабу Ягу, победили в музыкальном конкурсе Кота Баюна и вовремя завершили квест по поиску сундука Кащея Бессмертного! Настало время интеллектуальной схватки. Нечисть выставила Лешего, а ребята против него — отличника Лёшу.

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

Какое минимальное количество чисел из набора множителей от 1 до n нужно исключить, чтобы произведение оставшихся чисел не делилось на 2023?

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

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере дано n = 34.

34! = 295232799039604140847618609643520000000, действительно делится на 2023 нацело.

Если вычислить 33! = 8683317618811886495518194401280000000, то это число на 2023 уже не делится. Значит, достаточно вычеркнуть одно число.

Во втором примере дано n = 5.

5! = 120, не делится на 2023, ни одного числа вычеркивать не нужно.

Примеры тестов

Стандартный вход Стандартный выход
1
34
1
2
5
0

Задача 58. Спичек коробок

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Что это? — спичек коробок? —

Лучинок из берез?

И ты их не заметить мог? —

Ведь это ж грандиоз!

...

Игорь Северянин, "Поэза спичечного коробка", 1914 г.

Спички детям не игрушка, а средство обучения! Именно так считает руководитель школьного кружка по математике Игорь Васильевич. На сегодняшнем занятии ребята решали следующую задачу: какое наименьшее количество операций необходимо осуществить, чтобы превратить сложенное из спичек натуральное число a в натуральное число b? Под операцией понимается удаление, добавление или передвижение одной спички. Для определённости считайте, что разряды чисел должны остаться на своих местах (единицы старого числа должны стать единицами нового числа, десятки  — десятками и так далее, то есть новое число не может оказаться выше, ниже, левее или правее исходного). Цифры складываются из спичек следующим образом:

Формат входных данных

Две строки входного файла содержат различные натуральные числа a и b.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ a, b ≤ 109

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

Чтобы превратить число 2022 в 2023 достаточно передвинуть одну спичку в последнем разряде.

Примеры тестов

Стандартный вход Стандартный выход
1
2022
2023
1

Задача 59. Листок

Автор:Евгений Татаринов, Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Дубовый листок оторвался от ветки родимой

И в степь укатился, жестокою бурей гонимый:

Засох и увял он от холода, зноя и горя

И вот наконец докатился до Черного моря.

...

Михаил Лермонтов, "Листок", 1841 г.

Линия берега моря на координатной плоскости задана ветвью параболы y = x2. Листок имеет координаты (n, 0). Определите минимальное расстояние от листка до линии берега.

Формат входных данных

В единственной строке вводятся неотрицательное действительное число n.

Формат выходных данных

Выведите ответ на вопрос задачи с точностью не менее 3 знаков после запятой.

Ограничения

0 ≤ n ≤ 103

Примеры тестов

Стандартный вход Стандартный выход
1
0
0.0
2
1
0.537841449

Задача 60. Соседнее село

Автор:Антон Карабанов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Едем, едем в соседнее село на дискотеку,

Едем, едем на дискотеку со своей фонотекой,

Едем, едем с гаража угнав папину Победу,

Едем, едем в соседнее село на дискотеку.

...

Мурат Тхагалегов, "На дискотеку", 2014 г.

Видеоклип

В Энском районе n сёл и деревень. По странному стечению обстоятельств, между двумя населёнными пунктами есть дорога только в том случае, если в их названиях не менее k одинаковых букв. Например, при k = 6 (и менее) между novoogаrevo и domodedovo есть дорога (в каждом названии по 4 буквы "o" и по одной букве "v" и "e"), а при k = 7 (и более) — дороги нет.

Два населённых пункта считаются соседними, если между ними есть дорога. Определите наиболее предпочтительный населённый пункт для организации дискотеки, чтобы на неё могли добраться из как можно большего количества соседних сёл и деревень.

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и k. В следующих n строках расположены названия населённых пунктов si, состоящие из не более чем 250 строчных английских букв. Гарантируется, что все названия попарно различны.

Формат выходных данных

Выведите название одного из населённых пунктов из входных данных — ответ на вопрос задачи. Если подходящих ответов несколько — выведите лексикографичеси наименьший. Гарантируется, что входные данные таковы, что в Энском районе есть хотя бы одна дорога.

Ограничения

2 ≤ n ≤ 500

1 ≤ k ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснения к примерам

В первом примере при k = 1 дороги нет только между сёлами dedovo и myshkin (в из названиях нет ни одной общей буквы). Соответственно, эти два села будут соседними для четырёх населённых пунктов, а остальные четыре — для пяти. Из них лексикографически наименьшее babkino.

Во втором примере при k = 3 приведём граф дорог (смотри рисунок). При этом dedovo вообще не связан с остальными сёлами, у четырех сёл по три дороги, и только у koshkino их четыре.

Примеры тестов

Стандартный вход Стандартный выход
1
6 1
dedovo
babkino
vnukov
zhukovsk
koshkino
myshkin
babkino
2
6 3
dedovo
babkino
vnukov
zhukovsk
koshkino
myshkin
koshkino

Задача 61. Поручение

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Сказали Волу:

— Уважаемый Вол!

Отвезите, пожалуйста,

В школу Стол.

— Ну, вот ещё,

Охота была!

Найдем

Какого-нибудь

Осла!

Осел подумал:

«Зачем мне мучиться?

Ведь в школах

Ослы

Не учатся.

Поручу-ка я это дело

Барану!»

...

Борис Заходер, "Муравей", 1961 г.

Звери ленятся и стараются перепоручить доставку другим зверям, поменьше размером. С другой стороны, искать кого-то поменьше им ещё больше лень, поэтому если рядом никого подходящего нет, то проще доставить самому.

По имеющемуся списку длины n размеров животных, определите размер наиболее длинной возможной цепочки "поручений". Доставку можно перепоручить следующему в списке или через одного (то есть следующему за следующим) если такие есть, но только в том случае, если его размер строго меньше.

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество зверей. В следующей строке через пробел расположена перестановка натуральных чисел от 1 до n — их размеры.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 2, получат не менее 10 баллов.

Решения, верно работающие при n = 3, получат не менее 10 баллов.

Пояснение к примеру

В примере дано десять зверей. Наиболее длинная цепочка поручений равна 3, она получается из чисел 9, 5 и 2.

Примеры тестов

Стандартный вход Стандартный выход
1
10
10 1 4 9 5 6 2 8 3 7
3

Задача 62. Только точки

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

А вчера прислал по почте

Два загадочных письма:

В каждой строчке — только точки, —

Догадайся, мол, сама.

И кто его знает,

На что намекает.

...

Михаил Исаковский, "И кто его знает...", 1938 г.

Видеоклип

Формат входных данных

Три равных по длине строки входного файла содержат только символы "." (ASCII-код 46) и ":"(ASCII-код 58).

Формат выходных данных

Выведите строку.

Ограничения

Длины строк во входных данных не превосходят 250.

Система оценки и описание подзадач

Баллы за задачу начисляются только в случае, если все тесты успешно пройдены.

Примеры тестов

Стандартный вход Стандартный выход
1
:.::.:.:.:.:::...:.:
.:::.::..::.:::.:.::
::::.:.:..::::...:..
I LOVE YOU

Задача 63. Поле Чудес

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Не прячьте ваши денежки по банкам и углам,

Несите ваши денежки — иначе быть беде.

И в полночь ваши денежки заройте в землю там,

И в полночь ваши денежки заройте в землю, где?

...

Не горы, не овраги и не лес,

Не океан без дна и берегов,

А поле, поле, поле, поле Чудес,

А поле, поле, поле, поле Чудес,

Поле чудес в Стране Дураков.

Крекс-пекс-фекс…

Булат Окуджава, "Поле чудес в стране Дураков", 1975 г.

Песня из фильма "Приключения_Буратино"

 — Я тебе сейчас объясню. В Стране Дураков есть волшебное поле, — называется Поле Чудес... На этом поле выкопай ямку, скажи три раза: «Крекс, фекс, пекс», положи в ямку столько золотых, сколько захочешь, засыпь землёй, сверху посыпь солью, полей хорошенько и иди спать. Наутро из ямки вырастет небольшое деревце, а на нём вместо листьев будут висеть золотые монеты. Понятно?

 — И сколько же монет вырастет?

 — Зависит от того, сколько закопал. Но ты не переживай — ни одна монетка не пропадёт! Цифры числа зарытых монеток переставляются таким чудесным образом, чтобы получилось как можно большее число. Именно столько монеток утром соберёшь с волшебного деревца. Зароешь одну монетку — одна и вырастит, зароешь 12 — соберешь 21, ну а если, например, 19 не пожалеешь — наутро станешь богачом с 91 золотой монетой! Так что не скупись!

 — А если у меня сейчас ровно n золотых, как мне получить наибольшую прибыль?

Формат входных данных

Единственная строка входного файла содержит натуральное число n — количество денег у Буратино. Он может зарыть их все или разделить на две части и зарыть только одну, а другую спрятать в кармане. Зарытая часть преобразуется согласно описанной операции, спрятанная — не изменится, в сумме они составят новое количество денег Буратино.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно натуральное число — наибольшее возможное новое количество денег Буратино.

Ограничения

1 ≤ n ≤ 1015

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 105, получат не менее 35 баллов.

Пояснение к примерам

В первом примере у Буратино 12 монет. Ему выгоднее зарыть их целиком и наутро собрать с дерева 21 монету.

Во втором примере у Буратино 100 монет. Ему выгоднее разделить их на две части: зарыть 19 монет, a в карман спрятать 81 монету. 19 монет превратятся в 91, в сумме с 81 они составят 172.

Примеры тестов

Стандартный вход Стандартный выход
1
12
21
2
100
172

Задача 64. Друг Горацио

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Милые трагедии Шекспира!

Хроники английских королей!

Звон доспехов, ликованье пира,

мрак, и солнце, и разгул страстей.

Спорят благородство и коварство,

вероломство, мудрость и расчет.

И злодей захватывает царство.

И герой в сражение идет.

...

Маргарита Алигер, "Милые трагедии Шекспира", 1959 г.

Краткое содержание "Гамлета": все ключевые персонажи, кроме Горацио, умерли, большинство — от яда.

Гамлета ещё можно спасти и вся надежда только на вас! Для этого необходимо всего лишь сварить правильное лечебное зелье, состоящее из двух ингредиентов: противоядия и воды. Но чтобы зелье получилось хорошим, вам нужно, чтобы противоядие составляло не менее a% и не более b% от полного объема зелья, а вода — весь остальной объём.

За одно действие вы можете налить в котёл (изначально пустой) либо один литр противоядия, либо один литр воды. Через какое минимальное количество действий вы получите хорошее зелье?

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и b.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ a ≤ b ≤ 99

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при a = b, получат не менее 50 баллов.

Пояснение к примеру

В первом примере дано a = 25 и b = 25. Если вылить в котёл один литр противоядия и три литра воды, получится зелье с 25%-м содержанием противоядия. Потребуется 4 действия.

Во втором примере дано a = 30 и b = 35. Если вылить в котёл один литр противоядия и два литра воды, получится зелье с 33,33...%-м содержанием противоядия. Потребуется 3 действия.

Примеры тестов

Стандартный вход Стандартный выход
1
25 25
4
2
30 35
3

Задача 65. Мы играем

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Мы играем во что захотим,

Мы упали и летим и летим,

А куда не знаем до поры, до поры —

Мы слепые по законам игры.

...

Глеб Самойлов, "Нисхождение", 1992 г.

Шахматы втёмную — вариант классических шахмат, при игре в который каждый игрок видит только свои фигуры и те поля, на которые может перейти одна из его собственных фигур. В шахматы втёмную возможно играть при помощи компьютерных программ или специализированных шахматных веб-сайтов, когда оба игрока не видят экран друг друга, а за вывод видимых и невидимых полей отвечает программа. Без помощи компьютерных технологий играть можно при помощи трех шахматных наборов и рефери. Шахматы втёмную были изобретены датскими шахматистами-любителями в 1989 году.

Глеб и Вадим играют в шахматы втёмную. Затяжная партия подошла к финалу: у Глеба король и ферзь против одинокого короля Вадима. В классических шахматах белые бы без труда одержали победу, но здесь вражеского короля ещё нужно найти...

Формат входных данных

Первая строка входного файла содержит координаты белого короля в шахматной нотации ("символ цифра", без пробела), вторая — белого ферзя. Гарантируется, что координаты полей различны.

Формат выходных данных

Выведите одно натуральное число — количество различных полей, на которых может прятаться чёрный король.

Ограничения

a ≤ символ ≤ h

1 ≤ цифра ≤ 8

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

Смотри рисунок.

Примеры тестов

Стандартный вход Стандартный выход
1
d2
h2
38

Задача 66. Качается вагон

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

Качается вагон, стучат колёса глухо,

Так хочется сойти, но остановок нет.

От станции "Любовь" до станции "Разлука"

У нас с тобой билет, у нас с тобой билет.

...

Игорь Шаферан, "Как мы любили", 1977 г.

Видеоклип

Все станции на пути следования поезда пронумерованы натуральными числами в порядке возрастания. Станция отправления имеет номер 1, в пути поезд останавливается исключительно на станциях, номера которых делятся нацело на a или a + 2. На какой станции будет сделана n-я по счету остановка?

Формат входных данных

Две строки входного файла содержит натуральные числа a и n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи. Гарантируется, что ответ не превысит 1018.

Ограничения

2 ≤ a ≤ 109

1 ≤ n ≤ 1018

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 105, получат не менее 60 баллов.

Пояснение к примеру

В примере дано a = 3 (то есть поезд останавливается только на станциях, номера которых делятся нацело на числа 3 и 5). Необходимо узнать, на какой станции поезд остановится в десятый раз.

Остановки будут сделаны на станциях 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30 и так далее. Десятое число в этом списке — 21.

Примеры тестов

Стандартный вход Стандартный выход
1
3
10
21

Задача 67. Миллион роз

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Жил-был художник один,

Домик имел и холсты.

Но он актрису любил,

Ту, что любила цветы.

Он тогда продал свой дом —

Продал картины и кров —

И на все деньги купил

Целое море цветов.

Андрей Вознесенский, "Миллион роз", 1982 г.

Видеоклип

Актрисе нужно распределить все подаренные ей розы по букетам трех типов — в каждом из них может быть ровно a, b или c цветов.

Определите наибольшее количество роз, которые невозможно распределить по таким букетам.

Формат входных данных

Три строки входного файла содержат три натуральных числа: a, b и c. Гарантируется, что все они простые.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

2 ≤ a < b < c ≤ 97

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере a = 3, b = 7 и c = 13. Число n = 11 является наибольшим, при котором уравнение 3 × x + 7 × y + 13 × z = n неразрешимо в целых неотрицательных числах.

12 роз можно распределить требуемым образом, например сформировав 4 букета по 3 розы.

13 роз можно распределить требуемым образом, например сформировав 1 букет из 13 цветов, и так далее.

Можно доказать, что для любого n > 11 найдется подходящее распределение.

Примеры тестов

Стандартный вход Стандартный выход
1
3
7
13
11

Задача 68. Путаница

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Замяукали котята:

«Надоело нам мяукать!

Мы хотим, как поросята,

Хрюкать!»

А за ними и утята:

«Не желаем больше крякать!

Мы хотим, как лягушата,

Квакать!»

Корней Чуковский, "Путаница", 1926 г.

Путаница добралась и до чисел: x-й член последовательности Фибоначчи вдруг решил, что он равен d. Естественно, это вызвало цепную реакцию — все последующие члены этой последовательности тоже изменились. Выяснилось это случайно, когда обнаружилось, что k-й член последовательности равен n. Помогите математикам распутать путаницу и определить, какой член последовательности изменился первым и на сколько.

Напомним, что числа Фибоначчи — элементы числовой последовательности

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …

в которой первые два числа равны единицам, а каждое последующее число равно сумме двух предыдущих чисел.

Формат входных данных

Первая строка входного файла содержит натуральное число k — номер числа Фибоначчи. Вторая строка входного файла содержит целое число n — новое значение k-го числа Фибоначчи. Гарантируется, что новое значение не совпадает со старым.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите в первой строке одно натуральное число x — номер числа Фибоначчи, которое изменилось. Во второй строке выведите одно целое число — его новое значение d. Если подходящих ответов несколько, выведите ту пару чисел, у которой x меньше. Для определенности считайте, что самое первое число последовательности Фибоначчи не изменялось.

Ограничения

2 ≤ k ≤ 80

 − 1018 ≤ n ≤ 1018

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере десятый член последовательности оказался равен 50. Такое изменение могло быть вызвано тремя причинами:

1) сам десятый член последовательности стал равен 50;

2) девятый член последовательности решил стать равным 29;

3) шестой член последовательности решил стать равным 7. Других возможностей нет, выводим пару с меньшим исходным номером.

Примеры тестов

Стандартный вход Стандартный выход
1
10
50
6
7
2
3
0
2
-1

Задача 69. Единица! Кому она нужна?!

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

...

Единица — вздор, единица — ноль

...

Владимир Маяковский, поэма "Владимир Ильич Ленин", 1924 г.

Недавно на уроке информатики Тимофей узнал про двоичную систему счисления. Больше всего ему понравились двоичные числа, имеющие следующее представление: сначала идет группа единиц, потом группа нулей, потом снова группа единиц (под группой будем понимать любое натуральное количество элементов). Такие числа Тимофей называет 101-образными и старательно выписывает их в столбик в порядке возрастания.

Какое десятичное число, запись которого в двоичной системе счисления 101-образна, будет располагаться на n-ом месте в списке?

Формат входных данных

В единственной строке записано одно натуральное число n — порядковый номер 101-образного числа.

Формат выходных данных

Выведете одно натуральное число — соответствующее десятичное число.

Ограничения

1 ≤ n ≤ 20000

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: 0 ≤ n ≤ 500, баллы: 30. Гарантируется, что ответ не превысит 105.

Подзадача 2: нет дополнительных ограничений, баллы: 70. Гарантируется, что ответ не превысит 1018.

Пояснение к примеру

Комментарий к первому примеру: приведем ряд из десяти первых чисел, представление которых в двоичной системе счисления 101-образно:

510 = 1012;

910 = 10012;

1110 = 10112;

1310 = 11012;

1710 = 100012;

1910 = 100112;

2310 = 101112;

2510 = 110012;

2710 = 110112;

2910 = 111012.

Примеры тестов

Стандартный вход Стандартный выход
1
10
29

Задача 70. Дивное волненье

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Моцарт в легком опьяненье

Шел домой.

Было дивное волненье,

День шальной.

И глядел веселым оком

На людей

Композитор Моцарт Вольфганг

Амадей.

...

Давид Самойлов, "Дуэт для скрипки и альта", 1981 г.

Художественное исполнение

Моцарт в приподнятом расположении духа возвращается домой (ещё бы — две пьесы за два дня и две ночи, это не шутка). Встречая мужчину, он учтиво приподнимает шляпу, и его настроение повышается на a. Встречая женщину, он приветливо улыбается, и его настроение увеличивается на b. Сколько существует различных наборов встречных прохожих, если всего за время прогулки настроение композитора выросло на n?

Формат входных данных

Единственная строка входного файла содержит три натуральных числа a, b и n, записанных через пробел.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ a, b ≤ 1000

1 ≤ n ≤ 1015

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 105, получат не менее 40 баллов.

Пояснения к примерам

В первом примере a = 2, b = 3 и n = 15. Моцарт мог встретить:

1) 0 мужчин и 5 женщин;

2) 3 мужчин и 3 женщин.

3) 6 мужчин и 1 женщину.

Всего три набора.

Во втором примере настроение всегда увеличивается на чётное число, а n = 15 — нечётное.

Примеры тестов

Стандартный вход Стандартный выход
1
2 3 15
3
2
2 4 15
0

3.483s 0.015s 227