Задача A. Воробьянинов и афиши

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

Условие

"С утра по Васюкам ходил высокий худой старик в золотом пенсне и в коротких, очень грязных, испачканных клеевыми красками сапогах. Он наклеивал на стены рукописные афиши." (И.Ильф, Е.Петров. "Двенадцать стульев").

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

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

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

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

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

Ограничения

1 ≤ n, a, b ≤ 100

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

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

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

В первом примере на улице 10 домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на 2, то есть на дома с номерами 2, 4, 6, 8, 10. Вторым проходом он расклеил две афиши на дома, номера которых делятся на 3, то есть на дома с номерами 3 и 9. Дом номер 6 он пропустил — на нем афиша уже висит. Всего наклеено 7 афиш.

Во втором примере Воробьянинов не наклеит ни одной афиши.

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

Стандартный вход Стандартный выход
1
10 2 3
7
2
8 10 27
0

Задача B. Уникальные символы

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

Условие

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

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

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

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

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

Ограничения

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

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

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

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

Стандартный вход Стандартный выход
1
hello world
lo
2
gaudeamus igitur
gu

Задача C. Минимальное число

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

Условие

Тимофею подарили набор цифр. Он быстро научился составлять из них различные числа. Помогите Тимофею составить из всего набора цифр минимально возможное число.

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

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

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

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

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

Стандартный вход Стандартный выход
1
50120
10025
2
12
12
3
10
10

Задача D. Собеседование

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

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1018

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

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

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

Стандартный вход Стандартный выход
1
10
25
2
11
-1

Задача E. Теннисный корт

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

Условие

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

Теннисный матч состоит из сетов, сет состоит из геймов, каждый сет начинается со счета 0-0. Сет завершается победой игрока, первым выигравшим 6 геймов, при этом у соперника должно быть выиграно не более 4 геймов, в противном случае сет продолжается до того момента, пока кто-то из игроков не выиграет седьмой гейм. Другими словами, сет может завершиться со счетом 6-0, 6-1, 6-2, 6-3, 6-4, 7-5 и 7-6 в пользу одного из игроков. Игра заканчивается, когда один из игроков выиграет три сета.

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

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

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

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

Ограничения

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

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

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

Стандартный вход Стандартный выход
1
1111112212211212121212121222121
1-2
6-0
4-6
5-7
2-1
2
222222222222222222
0-3
0-6
0-6
0-6

Задача F. Треугольные и квадратные числа

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

Условие

Сегодня на занятии кружка по математике Тимофей узнал о существовании фигурных чисел. Больше всего его заинтересовали треугольные и квадратные числа.

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

На рисунке вы видите начало ряда треугольных чисел (1, 3, 6, 10, ...) и ряда квадратных чисел (1, 4, 9, 16, ...).

Тимофею нравится находить закономерности. Он смог доказать, что любое квадратное число (если оно больше 1) представимо в виде суммы всего двух треугольных чисел! Для поиска более сложных закономерностей ему нужно знать количество различных способов это сделать.

Помогите Тимофею! Найдите количество способов представления данного квадратного числа в виде суммы двух треугольных. Способы, отличающиеся порядком слагаемых, считаются одинаковыми.

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

В единственной строке входного файла записано одно натуральное квадратное число n.

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

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

Ограничения

4 ≤ n ≤ 1010

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

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

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

Комментарий к первому примеру: существует единственный способ представить 4 в виде суммы двух треугольных чисел: 4 = 3 + 1.

Комментарий ко второму примеру: существует два способа представить 16 в виде суммы двух треугольных чисел: 16 = 10 + 6 = 15 + 1.

Комментарий к третьему примеру: существует четыре способа представить 10000 в виде суммы двух треугольных чисел: 10000 = 5050 + 4950 = 5995 + 4005 = 8515 + 1485 = 9180 + 820.

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

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

Задача G. Мужик и два генерала

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

Условие

По сюжету сатирической сказки Михаила Салтыкова-Щедрина «Повесть о том, как один мужик двух генералов прокормил», два отставных генерала, выйдя на пенсию, неизвестным образом попадают на необитаемый остров. Они хотят выбраться с острова, однако не могут, поскольку даже не разбираются в сторонах света. Вскоре они решают найти мужика (то есть крестьянина), который сможет их вернуть домой. Генералы находят на острове мужика. Мужик строит для них лодку и переправляет через моря в Петербург. По прибытии в Петербург они наедаются, напиваются и едут в казначейство за деньгами. В благодарность за спасение с острова они посылают мужику рюмку водки и пятак серебра, восклицая: «Веселись, мужичина!».

Но у нас не сказка, а задача, да и генералы с тех пор слегка изменились, поэтому они будут помогать мужику строить лодку. Для её изготовления нужно n досок, каждый человек за один день способен сделать одну доску. Мужик, как архетип неутомимого народа, способен работать каждый день, а вот генералам нужен отдых, выходные и отпуск на море (хорошо, что место действия соответствует). Поэтому первый генерал работает a дней подряд, а потом b дней подряд отдыхает. Второй генерал работает c дней подряд, а потом d дней подряд отдыхает. Как скоро будет построена лодка?

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

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

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

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

Ограничения

1 ≤ n ≤ 1018.

1 ≤ a, b, c, d ≤ 1015.

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

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

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

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

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

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

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

В третий день работает только мужик, оба генерала отдыхают. Всего готово 6 досок.

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

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

В шестой день мужик и второй генерал делают по одной доске каждый, первый генерал отдыхает. Всего готово 11 досок - лодка построена. Работа завершена за 6 дней.

Во втором примере лодка строится за один день.

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

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

Задача H. В каждом рисунке - солнце

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

Условие

В столице Дальнего Востока проходит конкурс детских рисунков. Для оформления выставки работ финалистов организаторы планируют задействовать квадратный стенд. На одной стороне стенда будут размещены n вертикально ориентированных изображений одинакового размера w1 × h1. На второй стороне стенда будут размещены m горизонтально ориентированных изображений одинакового размера w2 × h2. При этом, согласно стандартам, расстояние между двумя рисунками, а также между рисунком и краем стенда должно быть не меньше 1, а стороны рисунков должны быть параллельны сторонам стенда.

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

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

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

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

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

Ограничения

0 ≤ n, m ≤ 109

1 ≤ w1, h1, w2, h2 ≤ 109

w1 ≤ h1

h2 ≤ w2

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

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

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

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

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

В примере нужно на одной стороне стенда разместить пять вертикально ориентированных рисунков размером 2 × 3 и четыре горизонтально ориентированных размером 5 × 1 на противоположной. Минимальный подходящий размер стенда 10, один из вариантов размещения изображений - на рисунке.

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

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

Задача I. Граф, но не Монте-Кристо

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

Условие

Наталья Васильевна — учитель информатики. Она замечательно объясняет материал, многие ее ученики набирают 100 баллов на ЕГЭ. Сегодня ей нужно повторить с ребятами задачу о поиске путей в графе. Помогите составить программу, вычисляющую ответ на поставленную задачу: на рисунке — схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в указанный город?

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

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

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

Выведите одно неотрицательное целое число — количество различных путей из города A в город, обозначенный n-й буквой английского алфавита.

Ограничения

1 ≤ n ≤ 26

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

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

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

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

Стандартный вход Стандартный выход
1
10 16
A B
B F
F J
B C
A C
C G
G J
A D
C D
D H
G H
H J
A E
D E
E I
I J
12

Задача J. Баскетбол

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

Условие

Тимофей с одноклассниками обожают играть в баскетбол и не пропускают ни одной возможности сыграть в эту замечательную игру. Вот и сегодня на большой перемене состоялась важная игра (за выход в 1/1024 финала Объединенного городского школьного турнира).

Игра начинается со счета 0:0. Каждая результативная атака может принести одной из двух команд 1, 2 или 3 очка.

Введем понятие "ход игры" — последовательность изменения счета на табло. Например, ход игры может быть таким: 0-0, 2-0, 2-1, 5-1, 5-3.

Когда учитель информатики по пути в учительскую заглянул в спортзал, счет на табло был a:b. А после звонка на урок был зафиксирован окончательный результат — счет c:d. Теперь на уроке информатики перед ребятами поставлена задача — определить, сколько существует ходов игры, в которых:

1) Начальный счет — 0:0;

2) Промежуточный счет — a:b;

3) Окончательный счет — c:d.

Помогите Тимофею и его одноклассникам!

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

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

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

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

Ограничения

0 ≤ a ≤ c ≤ 20 и 0 ≤ b ≤ d ≤ 20

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

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

Подзадача 1: a = 0, b = 0, c = 0, баллы: 15.

Подзадача 2: a = 0, c = 0, баллы: 15.

Подзадача 3: a = 0, b = 0, c = 1, баллы: 20.

Подзадача 4: a = 0, b = 0, баллы: 20.

Подзадача 5: нет ограничений, баллы: 30.

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

Комментарий ко второму примеру:

Комментарий к третьему примеру:

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

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

Задача K. Игра с палочками

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

Условие

На столе лежит n палочек. Двое по очереди берут палочки, допустимы следующие ходы:

1) можно забрать одну палочку;

2) если число палочек четно — можно забрать половину палочек;

3) если число палочек делится на три — можно забрать треть всех палочек или две трети всех палочек.

Проигрывает тот, кто не может сделать очередной ход.

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

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

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

Выведите 'First' или 'Second' (без кавычек), в зависимости от того, победит первый или второй игрок.

Ограничения

1 ≤ n ≤ 105

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

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

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

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

Задача L. Игра с ладьями

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

Условие

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

Бендер и одноглазый любитель играют в следующую игру. На доске находится n ладей. Игроки ходят по очереди, первым ходит Остап. За один ход игрок может убрать с доски не менее одной и не более половины всех оставшихся ладей. Например, если сейчас на доске 8 ладей, забрать можно от 1 до 4 ладей. Проигрывает тот, после чьего хода останется последняя ладья. Кто выиграет при правильной игре?

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

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

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

Выведите победителя - одно слово 'Bender' или 'One-eyed' (без кавычек).

Ограничения

2 ≤ n ≤ 109

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

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

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

В первом примере Бендер вынужден забрать одну ладью. На доске останется последняя ладья - Остап проиграл.

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

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

Стандартный вход Стандартный выход
1
2
One-eyed
2
8
Bender

Задача M. В чужом пиру - похмелье

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

Условие

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

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

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

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

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

Выведите титул победителя — "King" или "Queen" (без кавычек).

Ограничения

1 ≤ k, q, n ≤ 105

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

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

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

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

На пиру 13 рыцарей. Любимое число короля — 6, королевы — 4. Первым ходом король хвалит 6 рыцарей. После любых ответных ходов королевы ему нужно хвалить по одному рыцарю. Если же король первым ходом восславит одного рыцаря, то он проиграет.

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

Стандартный вход Стандартный выход
1
13 6 4
King

Задача N. Игра на перемене

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

Условие

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

1. Из кучи можно забрать одну любую монетку;

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

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

Выигрывает тот игрок, после хода которого в куче не останется ни одной монеты. Естественно, и Петя, и Вася стремятся выиграть, поэтому играют в полную силу.

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

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

В единственной строке входного файла через пробел записаны неотрицательные числа a, b, c — количества монет достоинством в один, два и пять рублей соответственно. Гарантируется, что a + b + c ≠ 0.

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

Выведите имя победителя игры — Petya или Vasya.

Ограничения

0 ≤ a, b, c ≤ 109

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

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

1.086s 0.022s 49