Гоняясь друг за дружкой по апельсиновой роще, коротышки обнаружили посреди деревьев полянку с большой четырехугольной площадкой для игры в шарашки. Здесь же был обнаружен целый набор деревянных молотков с длинными ручками и пара шарашек, то есть все, что требуется для этой увлекательной подвижной игры. Нужно сказать, что шарашкой у лунатиков называется большой деревянный шар, величиной с коротышечью голову. Выигрывает, разумеется, та команда, которая первой загонит в ямку свой шар.
Как только площадка была обнаружена, организовались сразу четыре команды шарашников, но поскольку все четыре не могли принимать участия в игре, то играли лишь две команды, а две другие стали ждать своей очереди.
Николай Носов, "Незнайка на Луне".
Коротышки договорились проводить чемпионаты по шарашкам. Каждый чемпионат состоял из трех игр. Сначала команда A играет с командой B. Потом команда C играет с командой D. В последней игре, в которой встречаются победители первых двух игр, определяется чемпион.
Вечером, после завершения финального матча какого-то чемпионата (коротышки сбились со счета, сколько их было за день), выяснилось, что команда A сыграла a матчей, команда B сыграла b матчей, а команда C сыграла c матчей. Поскольку за время пребывания на Дурацком острове коротышки заметно отупели, помогите им определить количество игр, которое провела команда D.
Формат входных данных
Три строки входного файла содержит натуральные числа a, b и c. Гарантируется непротиворечивость входных данных.
Формат выходных данных
Выведите натуральное число — ответ на задачу.
Ограничения
1 ≤ a, b, c ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при b = c, получат не менее 20 баллов.
Решения, верно работающие при a = b, получат не менее 20 баллов.
Пояснение к примеру
В примере был проведен единственный чемпионат. Команда A обыграла команду B. Потом команда C проиграла команде D. В финале встретились команды A и D. Значит команда D провела ровно две игры.
Ох уж эти уроки математики... Сегодня учитель Иван Иванович развлекался игрой в "Семёрки и девятки". Он записывал на доске два натуральных числа одинаковой длины n, первое — состоящее из одних семёрок, второе — состоящее из одних девяток, и требовал, чтобы класс ответил на вопрос, какая цифра будет на k-м месте в произведении этих чисел. Пока никто не пострадал от гнева Ивана Ивановича, напишите программу, находящую ответ на этот вопрос.
Формат входных данных
В двух строках входного файла записаны два натуральных числа: n и k.
Формат выходных данных
Выведите одну десятичную цифру — ответ на задачу.
Ограничения
1 ≤ n ≤ 109
1 ≤ k ≤ 2 × n
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 4, получат не менее 40 баллов.
Пояснение к примеру
В примере n = 1 и k = 2. Перемножаются два однозначных числа 7 и 9, учителя интересует вторая цифра произведения 7 × 9 = 63. Это цифра 3.
"Abcde (произносится Эбсиди) — женское имя в США. По состоянию на 2017 год 373 девушки носят это редкое имя. Оно образовано из первых пяти букв английского алфавита по порядку и не имеет другого происхождения или значения," — сообщает Википедия.
Будем называть имя редким, если оно так же, как и Abcde образовано буквами английского алфавита по порядку. Например, имена Abc, X, Pqrst — редкие, а Denis, Cab, Za и Dfg — нет.
Родители хотят дать своему первенцу редкое имя, используя только буквы собственных имен. Определите для них наиболее длинное возможное редкое имя для ребенка.
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: m и f — длины имен родителей. В следующих двух строках расположены сами имена, во второй строке длины m, в третьей — длины f из строчных английских букв.
Формат выходных данных
Выведите одну строку из строчных английских букв — ответ на вопрос задачи. Если существует несколько подходящих имен — выведете лексикографически меньшее, то есть то, которое начинается с буквы, расположенной ближе к началу алфавита.
Ограничения
1 ≤ m, f ≤ 100
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при m = f = 1, получат не менее 20 баллов.
Тимофей заполнил прямоугольную таблицу размером n × m следующим образом: в левую верхнюю ячейку записал цифру d, в ячейку правее — цифру d + 1, в следующую — цифру d + 2 и так далее. Если на каком-то шаге ему нужно было записать число 10, вместо нее он записывал одну цифру 0.
Числа в остальных строках он заполнил следующим образом: каждое число в ячейке равнялось числу в ячейке выше, увеличенному на 1. Опять же, вместо 10 он записывал 0.
На рисунке ниже Вы видите заполненный цифровой прямоугольник при n = 5, m = 12 и d = 3.
Теперь Тимофей хочет узнать, сколько цифр каждого вида находится в прямоугольнике.
Формат входных данных
Первые две строки входного файла содержит два натуральных числа: n и m — размеры таблицы. В третьей строке содержится десятичная цифра d, расположенная в левой верхней ячейке цифрового прямоугольника.
Формат выходных данных
Выведите через пробел десять чисел — количество цифр от 0 до 9 в таблице.
Ограничения
1 ≤ n, m ≤ 109
0 ≤ d ≤ 9
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n = m = 1, получат не менее 5 баллов.
Решения, верно работающие при n, m ≤ 100, получат не менее 30 баллов.
Решения, верно работающие при n = 1, получат не менее 20 баллов.
Решения, верно работающие при n ≤ 10, получат не менее 20 баллов.
Пояснение к примеру
Смотри рисунок.
Примеры тестов
№
Стандартный вход
Стандартный выход
1
5
12
3
5 5 5 6 7 7 7 7 6 5
Задача E. Двоичные числа с чередующимися цифрами
≡
Тимофей очень любит двоичные числа, в которых единицы и нули чередуются, например 1, 10, 101, 1010, 10101 и так далее. Все такие числа (в единственном экземпляре) он аккуратно хранит на карточках в специальном альбоме.
Сегодня Тимофей хочет представить десятичное число n в виде суммы чисел из альбома. Поскольку ему жалко расставаться со своими числами, он хочет найти наименьшее число своих карточек, числа на которых в сумме дают n. Сколько карточек понадобится Тимофею?
Формат входных данных
Единственная строка входного файла содержит одно натуральное десятичное число n.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу. Если число n невозможно представить в виде суммы имеющихся чисел — выведите число -1.
Ограничения
1 ≤ n ≤ 1015
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 100, получат не менее 40 баллов.
Решения, верно работающие при 1 ≤ n ≤ 105, получат не менее 80 баллов.
Пояснения к примерам
В первом примере число 23 можно представить в виде суммы чисел 21 (101012) и 2 (102). Всего два слагаемых.
Во втором примере нет возможности представить число 9 в виде суммы чисел из альбома.
