В финале крупнейшего спортивного турнира "Хрустальная ракетка" на главном корте встретились два лучших теннисиста современности. Тысячи зрителей стали свидетелями яркого противостояния, красивых розыгрышей, блистательных подач, умопомрачительных сэйвов, отчаянных прыжков и ... энергетического коллапса, выразившегося в отключении света. Когда яркие прожекторы вновь зажглись, выяснилось, что все компьютерные данные о ходе матча не сохранились. Хорошо, что резервный судья отмечал на листочке кто из соперников какой гейм выиграл. Помогите организаторам и восстановите счет на главном табло теннисного корта!
Теннисный матч состоит из сетов, сет состоит из геймов, каждый сет начинается со счета 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".
Генералиссимус Флатландских вооруженных сил проводил совещание со своим заместителем. Основным вопросом обсуждения стало состояние непобедимой танковой армады наиболее вероятного противника - Берляндии. Перед вами отрывок из стенограммы заседания.
- Итак, коллеги, резюмируем. Мы не знаем, сколько танков у Берляндии. Даже примерно. Наш разведчик сообщил, что ему удалось тайком сфотографировать один из танков с бортовым номером, давайте думать, какую информацию мы сможем из этого извлечь.
- Шеф, нам известна система нумерации танков берляндских вооруженных сил. Бортовой номер состоит из трех частей. Первое число - порядковый номер танкового батальона, второе число - порядковый номер роты в батальоне и третье число - порядковый номер танка в роте. Все числа могут иметь ведущие нули. Например, если в роте 150 танков, третье число на борту будет написано так: (001, 002, ..., 010, ..., 100, ..., 150). Лишних ведущих нулей они не пишут, поэтому, если, например, третье число на танке 04, значит в каждой роте не меньше десяти, и не более 99 танков.
- Значит, если номер танка 12-3-04, то у противника от 12 до 99 батальонов, в каждом из них от 3 до 9 рот (нам ведь точно известно, что Берляндцы зациклены на порядке, и у них всё в армии одинаковое), а в каждой роте от 10 до 99 танков. Где мой калькулятор? Получается, что по этому номеру мы определим, что в Берляндии от 360 до 88209 танков.
Бесшумно появившейся адъютант положил перед Генералиссимусом запечатанный конверт и так же тихо удалился.
- Вот и долгожданная фотография! Посмотрим...
Очень долгая пауза.
- Шеф, у нас две проблемы. Первая - берляндцы не используют разделители в бортовых номерах. Действительно - зачем им это? Они и так знают, сколько у них батальонов, рот и танков в каждой роте. Вторая - судя по длине номера, танков у них очень много.
- Что верно, то верно... Передайте номер нашему программисту, пусть найдет наименьшее возможное количество танков хитрых берляндцев!
Формат входных данных
Единственная строка входного файла содержит натуральное число n - бортовой номер танка. Гарантируется наличие в номере не менее трех цифр, отличных от нуля.
Формат выходных данных
Выведите одно натуральное число - минимальное достоверное количество танков в Берляндии.
Ограничения
111 ≤ n ≤ 1015
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере n = 123. Разделители можно расставить единственным образом: 1-2-3. В Берляндии не менее одного батальона, не менее двух рот в каждом батальоне, не менее трех танков в каждой роте. Итого у противника не менее 6 танков.
Во втором примере n = 1024. Есть три возможности расставить два разделителя.
Первая: 10-2-4. В Берляндии не менее десяти батальонов, не менее двух рот в каждом, не менее четырёх танков в каждой. Итого у противника не менее 80 танков.
Вторая: 1-02-4. В Берляндии не менее одного батальона, не менее десяти рот в каждом, не менее четырёх танков в каждой. Итого у противника не менее 40 танков.
Третья расстановка 1-0-24 невозможна - нумерация в армии Берляндии начинается с 1, поэтому рота не может иметь номер 0 (а также 00, 000 и так далее). В итоге можно с уверенностью утверждать, что независимо от расстановки разделителей, хотя бы 40 танков у противника точно имеется.
Команда игроков участвует в соревновании "Форт Боярд". После долгой борьбы за ключи и подсказки, тяжелых конкурсов и загадок старца Фура, побегов из тюрьмы и совета Теней, участники игры добрались до Сокровищницы. Теперь они должны разгадать кодовое слово и обозначить составляющие его буквы при помощи пушечных ядер на алфавитном полу Сокровищницы. Если предложенный вариант окажется правильным, игроки получают доступ к золотым монетам, и могут попытаться вынести наружу как можно большее их количество.
Капитан команды считает, что загаданное организаторами кодовое слово - s. Помогите ему определить количество способов расставить ядра на полу сокровищницы для проверки.
Формат входных данных
Первая строка входного файла содержит одно английское слово s, записанное строчными буквами. Вторая строка содержит два натуральных числа, записанных через пробел: n и m - количество строк и столбцов на алфавитном полу. В следующих n строках записано по m строчных английских букв - описание пола.
Формат выходных данных
Выведите одно неотрицательное целое число - ответ на задачу. Гарантируется, что ответ не превысит 1018.
Ограничения
1 ≤ n, m ≤ 20
1 ≤ len(s) ≤ 50
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере участники могут выбрать одно из двух положений ядра для символа 'u' и одно из двух положений для символа 'e'. Остальные символы можно выбрать единственным образом.
В магазин завезли n единиц товара. Каждая единица товара характеризуется двумя параметрами: сортом и свежестью. В очередь за этим товаром выстроились n покупателей. Каждый покупатель имеет предпочтение либо в сорте, либо в свежести, и выбирает наилучший товар с этим параметром из оставшихся. Определите, кому какая единица товара будет продана.
Формат входных данных
Первая строка входного файла содержит натуральное число n - количество единиц товара и покупателей. Во второй строке задана строка длиной n, состоящая из символов '0' и '1'. Символ '0' соответствует событию "покупатель предпочтёт товар с самым высоким сортом", символ '1' соответствует событию "покупатель предпочтёт товар самой высокой свежести". В следующих n строках через пробел расположены два целых числа xi, yi - значения сорта и свежести товара с номером i. Гарантируется, что нет двух единиц товаров с одинаковым сортом. Гарантируется, что нет двух единиц товаров с одинаковой свежестью.
Формат выходных данных
Выведите через пробел перестановку n чисел - порядок, в котором будут продан весь товар.
Ограничения
1 ≤ n ≤ 105
1 ≤ xi, yi ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие в случае, когда все покупатели выбирают товар с наивысшим сортом, получат не менее 20 баллов.
Решения, верно работающие при 1 ≤ n ≤ 103, получат не менее 60 баллов.
Пояснение к примеру
В примере первый покупатель предпочитает самый высокий сорт и выберет товар под номером 3 (у него самый высокий сорт - 14). Второй покупатель тоже предпочитает самый высокий сорт и выберет товар под номером 1 (у него самый высокий сорт из оставшихся - 12). Третий покупатель предпочитает свежесть и выберет товар под номером 2 со свежестью 36. Четвертый покупатель заберет четвертый товар с сортом 8, пятый - оставшийся пятый товар с сортом 1.
В каждый из n дней в одно и то же время в акваторию морского порта прибывает новое судно с товаром, который нужно разгрузить. Этот процесс занимает двое суток для каждого корабля, после чего судно отправляется дальше. Одновременно разгружаться может только одно судно и прерывать этот процесс нельзя. Среди товаров встречаются скоропортящиеся, которые нужно разгрузить как можно раньше, поэтому как только очередное судно покидает порт, под разгрузку встаёт корабль с самым скоропортящимся товаром. Определите для каждого корабля номер дня, в который он покинет порт.
Формат входных данных
Первая строка входного файла содержит натуральное число n - количество кораблей, нуждающихся в разгрузке. Во второй строке через пробел указана срочность разгрузки судна ai, прибывшего в акваторию порта в день номер i - чем она выше, тем раньше следует разгрузить корабль. Гарантируется, что все числа во второй строке различны.
Формат выходных данных
Выведите через пробел n натуральных чисел bi - номера дней, в который i-й корабль покинет порт.
Ограничения
1 ≤ n ≤ 50000
1 ≤ ai ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 1000, получат не менее 60 баллов.
Пояснение к примеру
События в примере будут развиваться следующим образом:
В первый день прибывает первое судно и сразу встает под разгрузку.
Во второй день прибывает второе судно и ждет очереди на разгрузку. Продолжается разгрузка первого судна.
В третий день прибывает третье судно. Завершается разгрузка первого судна. Оно покидает порт в день номер 3. Из двух кораблей, ожидающих разгрузки, более высокий приоритет у того, которое прибыло только что и оно встаёт под разгрузку.
В четвёртый день прибывает последнее судно. Продолжается разгрузка судна номер 3.
В пятый день его разгрузка завершается и судно номер 3 покидает порт. Из двух кораблей, ожидающих разгрузки, более высокий приоритет у того, которое прибыло во второй день - оно встаёт под разгрузку.
В шестой день продолжается разгрузка второго судна.
В седьмой день завершается разгрузка второго судна. Оно покидает порт в день номер 7. Под разгрузку встаёт последнее судно, которое покинет порт в день номер 9.
У Тани - свадебный переполох! Выбор платья, фаты, цветов, ресторана, музыки - всему нужно успеть уделить время! Времени мало, а дел много.
Сегодня невеста выбирает свадебный торт. Конечно, он должен быть красивым, вкусным и, самое главное, - многоэтажным. Согласно представлениям Тани об идеальном торте, на вершине должен располагаться корж радиуса 1, под ним - корж радиуса a или b, под ним (и каждым следующим) - корж радиусом в a или b раз больше предыдущего. Например, при a = 2 и b = 3 идеальный торт может быть таким: 1-2-6-12-24-... Или таким: 1-3-6-18-36-... Или таким: 1-3-9-27-81-...
Максимальный радиус нижнего коржа торта не может превышать r - в противном случае его невозможно будет вынести из кондитерского цеха. Помогите Тане - посчитайте по известным a, b и r количество идеальных тортов. Естественно, высота каждого такого отдельного торта должна быть максимально возможной, при этом высоты двух различных идеальных тортов могут отличаться. Два торта считаются различными, если перечисление их радиусов не совпадает хотя бы в одной позиции.
Формат входных данных
Первая строка входного файла содержит три натуральных числа, записанных через пробел: a, b и r.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу. Гарантируется, что он не превысит 1015.
Ограничения
2 ≤ a < b < r ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере Таня посчитает идеальными следующие пять тортов:
