Автор этой задачи в детстве частенько играл дома в футбол, стуча мячом в стенку между своей квартирой и квартирой, находящейся в соседнем подъезде. В конце концов соседям это надоело, и они пожаловались маме. Так я узнал и навсегда запомнил номер квартиры своих соседей из другого подъезда. А теперь задача...
В многоэтажном доме в каждом подъезде на каждом этаже по k квартир. Антон, живущий в квартире №n, стучит мячом в стенку жильцам из соседнего подъезда, живущим в квартире №m. На каком этаже они живут?
Формат входных данных
В трех строках входного файла содержится три натуральных числа: k, n и m. Гарантируется непротиворечивость входных данных.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу.
Ограничения
1 ≤ k ≤ 105
k ≤ n < m ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при k = 1, получат не менее 10 баллов.
Решения, верно работающие при k = 2, получат не менее 20 баллов.
Тимофей очень любит строковые переменные. Он умеет вычислять редакционное расстояние, строить дерево палиндромов и пугать одноклассниц страшным словом "хеширование". Изучив все чужие способы обработки строк, юный программист твердо решил облагодетельствовать человечество своим фундаментальным трудом — алгоритмом Тимофея.
Для начала он определил функцию сложностьслова. Слово в терминологии Тимофея — последовательность символов, являющихся строчными английскими буквами. Сложность слова, состоящего из единственной буквы, равна 1. Для более длинных слов Тимофей находит сумму сложностей всех сочетаний соседних букв в слове. Согласно его представлениям, сложность сочетания, в котором:
первая буква согласная, а вторая гласная, равна 1;
первая буква гласная, а вторая согласная, равна 2;
обе буквы гласные, равна 5;
обе буквы согласные, равна 7.
Гласными буквами Тимофей считает "a", "e", "i", "o", "u" и "y".
Например, для слова son Тимофей вычислит сложность сочетаний "so" (1) и "on" (2), сложит их и получит результат 3. Но сложность слова еще и напрямую зависит от его длины, поэтому Тимофей умножает полученный результат на длину слова (тоже 3) и получает окончательный ответ: сложность слова son равна 9. Пока Тимофей занят обдумыванием дальнейших действий, реализуйте эту функцию: по заданному слову определите его сложность.
Формат входных данных
Первая строка входного файла содержит длину слова s. Вторая строка входного файла содержит само слово s, состоящее из строчных английских букв.
Формат выходных данных
Выведите одно натуральное число — сложность данного слова.
Тимофей нарисовал на клетчатом листочке квадрат с диагональю a клеток. Затем он заштриховал вертикальными линиями по сетке его внутреннюю часть за исключением квадрата с диагональю b клеток. Определите длину всех проведенных штриховых линий.
Формат входных данных
Две строки входного файла содержат два натуральных числа: a и b — диагонали квадратов. Гарантируется четность a и b.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу.
Ограничения
2 ≤ b < a ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при a − b = 2, получат не менее 20 баллов.
Тимофей выписал в ряд все степени двойки в порядке возрастания: 1, 2, 4, 8, 16, 32 и так далее. Потом его заинтересовал вопрос, возможно ли заданное число представить в виде суммы некоторых подряд идущих чисел этого ряда? Оказалось, что некоторые числа представить можно (например 14 = 2 + 4 + 8), а некоторые — нет (например 13). Помогите Тимофею найти количество чисел, не превосходящих n, которые можно представить подобным образом.
Формат входных данных
Первая строка входного файла содержит единственное натуральное число n.
Формат выходных данных
Выведите натуральное число — ответ на задачу.
Ограничения
1 ≤ n ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 1000, получат не менее 30 баллов.
Решения, верно работающие при n ≤ 105, получат не менее 60 баллов.
Пояснение к примеру
В примере дано n = 10. Существует всего три числа, не превосходящих 10, которые нельзя представить подобным образом, это 5, 9 и 10.
Тимофей очень хочет сыграть в городки. Одна беда — для игры ему нужно как можно больше одинаковых цилиндрических чурок. В распоряжении Тимофея есть заготовки в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить набор для игры.
Если длина цилиндра является четным числом, Тимофей может распилить его пополам и получить два цилиндра вдвое меньшей длины. Распиливать уже распиленные ранее заготовки Тимофею лень, и он переходит к следующему цилиндру. Задача Тимофея — получить наибольшее количество цилиндров какого-нибудь одного размера. Если таких размеров несколько, Тимофей выберет для игры наименьший.
Формат входных данных
В первой строке входного файла записано одно натуральное число: n — количество заготовок.
Во второй строке входного файла через пробел записаны n целых чисел a1, ..., an в неубывающем порядке — длины цилиндров.
Формат выходных данных
Выведите через пробел два натуральных числа — наибольшее количество получившихся чурок одного размера и сам этот размер.
Ограничения
1 ≤ n ≤ 105
1 ≤ ai ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n = 1, получат не менее 10 баллов.
Решения, верно работающие при n = 2, получат не менее 10 баллов.
Решения, верно работающие при n, ai ≤ 103, получат не менее 85 баллов.
Пояснения к примерам
Комментарий к первому примеру. У Тимофея пять цилиндров длиной от 1 до 5. Тимофей распилит пополам цилиндр длины 2 и в его распоряжении окажется три одинаковых цилиндра длины 1. Он мог распилить пополам цилиндр длины 4 и получить три одинаковых цилиндра длины 2, но для игры он предпочтет взять более короткие цилиндры.
