"С утра по Васюкам ходил высокий худой старик в золотом пенсне и в коротких, очень грязных, испачканных клеевыми красками сапогах. Он наклеивал на стены рукописные афиши." (И.Ильф, Е.Петров. "Двенадцать стульев").
Ипполит Матвеевич ходит вдоль улицы из n домов и расклеивает афиши. Сначала он наклеил афиши на каждый дом, номер которого делился без остатка на a. Поскольку афиш осталось еще много, он вторым проходом наклеил афиши на каждый дом, номер которого делился без остатка на b. При этом, если на доме уже была наклеена афиша, новую Воробьянинов не клеил. Сколько всего афиш расклеил бывший предводитель дворянства?
Формат входных данных
Единственная строка входного файла содержит три натуральных числа: n — количество домов на улице, a и b — выбранные Воробьяниновым числа.
Формат выходных данных
Выведите одно неотрицательное целое число — количество расклеенных афиш.
Ограничения
1 ≤ n, a, b ≤ 100
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере на улице 10 домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на 2, то есть на дома с номерами 2, 4, 6, 8, 10. Вторым проходом он расклеил две афиши на дома, номера которых делятся на 3, то есть на дома с номерами 3 и 9. Дом номер 6 он пропустил — на нем афиша уже висит. Всего наклеено 7 афиш.
Во втором примере Воробьянинов не наклеит ни одной афиши.
Это простая учебная задача на строки. Просто убедитесь, что умеете их обрабатывать.
Формат входных данных
Единственная строка входного файла содержит две непустые строки, записанных через пробел и состоящих только из маленьких английских букв.
Формат выходных данных
Выведите одну строку, состоящую из символов, содержащихся и в первой, и во второй строке. Гарантируется наличие хотя бы одного такого символа. Каждый такой символ должен быть представлен один раз. Символы должны быть упорядочены в лексикографическом порядке.
Тимофею подарили набор цифр. Он быстро научился составлять из них различные числа. Помогите Тимофею составить из всего набора цифр минимально возможное число.
Формат входных данных
В единственной строке входного файла записано одно натуральное число: n — набор цифр, подаренных Тимофею. (1 ≤ n ≤ 1000000000).
Формат выходных данных
Выведите одно натуральное число — минимально возможное число, составленное из того же набора цифр.
Тимофей проходит собеседование по поводу устройства на работу в Очень Крупную Компанию на должность программиста. Ему предложили несложное испытание — написать программу, которая находит наименьшее натуральное число, произведение цифр которого равно n. Поскольку Тимофей очень волнуется, помогите ему справиться с этим заданием.
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу. Если такого числа не существует, выведите -1.
В финале крупнейшего спортивного турнира "Хрустальная ракетка" на главном корте встретились два лучших теннисиста современности. Тысячи зрителей стали свидетелями яркого противостояния, красивых розыгрышей, блистательных подач, умопомрачительных сэйвов, отчаянных прыжков и ... энергетического коллапса, выразившегося в отключении света. Когда яркие прожекторы вновь зажглись, выяснилось, что все компьютерные данные о ходе матча не сохранились. Хорошо, что резервный судья отмечал на листочке кто из соперников какой гейм выиграл. Помогите организаторам и восстановите счет на главном табло теннисного корта!
Теннисный матч состоит из сетов, сет состоит из геймов, каждый сет начинается со счета 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, 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.
По сюжету сатирической сказки Михаила Салтыкова-Щедрина «Повесть о том, как один мужик двух генералов прокормил», два отставных генерала, выйдя на пенсию, неизвестным образом попадают на необитаемый остров. Они хотят выбраться с острова, однако не могут, поскольку даже не разбираются в сторонах света. Вскоре они решают найти мужика (то есть крестьянина), который сможет их вернуть домой. Генералы находят на острове мужика. Мужик строит для них лодку и переправляет через моря в Петербург. По прибытии в Петербург они наедаются, напиваются и едут в казначейство за деньгами. В благодарность за спасение с острова они посылают мужику рюмку водки и пятак серебра, восклицая: «Веселись, мужичина!».
Но у нас не сказка, а задача, да и генералы с тех пор слегка изменились, поэтому они будут помогать мужику строить лодку. Для её изготовления нужно 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 дней.
В столице Дальнего Востока проходит конкурс детских рисунков. Для оформления выставки работ финалистов организаторы планируют задействовать квадратный стенд. На одной стороне стенда будут размещены 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, один из вариантов размещения изображений - на рисунке.
Наталья Васильевна — учитель информатики. Она замечательно объясняет материал, многие ее ученики набирают 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
Тимофей с одноклассниками обожают играть в баскетбол и не пропускают ни одной возможности сыграть в эту замечательную игру. Вот и сегодня на большой перемене состоялась важная игра (за выход в 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
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
"Остап проиграл подряд пятнадцать партий, а вскоре еще три. Оставался один одноглазый. В начале партии он от страха наделал множество ошибок и теперь с трудом вел игру к победному концу. Остап, незаметно для окружающих, украл с доски черную ладью и спрятал ее в карман." (И.Ильф, Е.Петров. "Двенадцать стульев").
Бендер и одноглазый любитель играют в следующую игру. На доске находится n ладей. Игроки ходят по очереди, первым ходит Остап. За один ход игрок может убрать с доски не менее одной и не более половины всех оставшихся ладей. Например, если сейчас на доске 8 ладей, забрать можно от 1 до 4 ладей. Проигрывает тот, после чьего хода останется последняя ладья. Кто выиграет при правильной игре?
Формат входных данных
Единственная строка входного файла содержит одно натуральное число: n - начальное количество ладей на доске.
Формат выходных данных
Выведите победителя - одно слово 'Bender' или 'One-eyed' (без кавычек).
Ограничения
2 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере Бендер вынужден забрать одну ладью. На доске останется последняя ладья - Остап проиграл.
Во втором примере первым ходом Бендер заберет три ладьи, на доске останется пять. Независимо от хода противника (тот заберет одну или две фигуры), Остап сможет оставить ему после своего второго хода две ладьи на доске и выиграть.
Король и королева пригласили на пир 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 рыцарей. После любых ответных ходов королевы ему нужно хвалить по одному рыцарю. Если же король первым ходом восславит одного рыцаря, то он проиграет.
Получив от родителей деньги на школьные завтраки, закадычные друзья Петя и Вася решили сыграть в свою традиционную игру "Coins". Они выбрали все свои монетки достоинством в один, два и пять рублей и сложили в одну кучу. Каждый из игроков ходит по очереди. Первым всегда ходит Петя. В игре допустимы следующие ходы:
1. Из кучи можно забрать одну любую монетку;
2. Можно вытащить из кучи одну монетку достоинством в два рубля (если она там есть), разменять ее у друзей и положить в кучу две монетки достоинством в один рубль;
3. Можно вытащить из кучи одну монетку достоинством в пять рублей (если она там есть), разменять ее у друзей и положить в кучу две монетки достоинством в два рубля и одну монетку достоинством в один рубль.
Выигрывает тот игрок, после хода которого в куче не останется ни одной монеты. Естественно, и Петя, и Вася стремятся выиграть, поэтому играют в полную силу.
Наблюдавший за игрой Тимофей внезапно заявил, что может определить победителя еще до первого хода, просто зная количество монеток каждого достоинства в куче. А вы сможете?
Формат входных данных
В единственной строке входного файла через пробел записаны неотрицательные числа a, b, c — количества монет достоинством в один, два и пять рублей соответственно. Гарантируется, что a + b + c ≠ 0.
