Согласно современным правилам игры в настольный теннис, после каждых двух засчитанных очков принимающий игрок должен стать подающим и так до конца партии или до тех пор, пока каждый из соперников не наберет по 10 очков, когда чередование смены подающего и принимающего остается таким же, но только после каждого очка. Например, играют Петя и Вася. Сначала подающим является Петя и он первым вводит мяч в игру при первом и втором розыгрыше очка. После этого подающим становится Вася и он первым вводит мяч в игру при третьем и четвертом розыгрыше очка. Потом опять первым подает Петя два раза, потом снова Вася два раза, и так далее. Если игра дошла до 21 розыгрыша очка (а партию выигрывает игрок, первым набравший 11 очков, если только оба игрока не набрали по 10 очков - в этом случае партия будет выиграна игроком, который первым наберет на 2 очка больше соперника), то Петя подает уже не по два раза подряд а всего один. После этого подает Вася тоже один раз, и так далее, пока партия не завершится.
Сейчас в партии должна осуществится n-я подача. Первым подавал Петя, а кто должен подавать сейчас?
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите имя подающего - "Petya" или "Vasya" без кавычек.
Ограничения
1 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере разыгрывается третья подача. Первые две сделал Петя, сейчас очередь Васи.
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число k и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Формат входных данных
Единственная строка входного файла содержит натуральное число k.
Формат выходных данных
Выведите натуральное число - ответ на задачу.
Ограничения
3 ≤ k ≤ 1015
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ k ≤ 1000, получат не менее 40 баллов.
Тимофей обожает участвовать в лотерее "Счастливый квадрат". Участники конкурса покупают билет, на котором в форме квадрата расположены числа от 1 до n2. Каждый участник покупает билет с числовым квадратом, закрашивает внутри него свой квадрат со стороной m, высылает свой вариант организаторам по почте и ждет тиража.
Сегодня ночью Тимофею приснился сон, который он считает вещим - в нём мальчику по секрету сообщили, что в закрашенном квадрате обязательно должно содержаться число k. Помогите Тимофею определить минимальное число билетов, которое ему необходимо приобрести для гарантированного выигрыша.
Формат входных данных
Единственная строка входного файла содержит три натуральных числа, записанных через пробел: n, m и k.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу.
Лена забыла пароль для входа в Windows XP, но помнила алгоритм его получения из символов строки s: если из неё удалить все k1 и k2 значные числа, то полученная последовательность и будет паролем.
Помогите Лене восстановить её пароль.
Формат входных данных
Первая строка входного файла содержит записанные через пробел два натуральных числа k1 и k2 - длины чисел, которые нужно удалить. Вторая строка содержит строку s. Строка s может содержать десятичные цифры от 1 до 9 и символы английского алфавита (как строчные, так и заглавные).
Формат выходных данных
Выведите пароль Лены - ответ на задачу. Гарантируется, что он содержит хотя бы один символ.
Ограничения
1 ≤ k1 < k2 ≤ 10
1 ≤ len(s) ≤ 105
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ len(s) ≤ 100, получат не менее 40 баллов.
Евгений разработал шифр для обмена сообщениями с друзьями. Пока шифр работает только для чисел по следующему алгоритму:
1) Заданное натуральное число разбивается на цифры.
2) Каждая цифра переводится в двоичную систему счисления.
3) Двоичные записи записываются подряд без пробелов.
Например, для числа 195 алгоритм сработает так: 195 - 1 9 5 - 1 1001 101 - 11001101.
Евгений зашифровал одно натуральное число и получил двоичную запись длины n, в которой единицы и нули чередуются. Эту запись он передал своему другу Артёму, а через несколько минут получил от него сообщение, в котором говорилось, что этот шифр никуда не годится, поскольку существует несколько чисел, которые будут зашифрованы одинаково. Более того, Артём точно указал количество таких чисел! Попробуйте написать программу, определяющую это количество.
Формат входных данных
Единственная строка входного файла содержит натуральное число n - длину двоичной записи чередующихся единиц и нулей.
Формат выходных данных
Выведите одно натуральное число - количество различных чисел, которые можно зашифровать такой записью. Гарантируется, что ответ не превысит 1018
Ограничения
1 ≤ n ≤ 90
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 10, получат не менее 18 баллов.
Пояснение к примеру
В примере дано n = 3, значит двоичная запись имеет вид 101. Существует три числа, которые могут быть зашифрованы таким образом: 5, 21 и 101.
