Алгоритм Луна — алгоритм вычисления контрольной цифры номера пластиковой карты в соответствии со стандартом ISO/IEC 7812. Не является криптографическим средством, а предназначен в первую очередь для выявления ошибок, вызванных непреднамеренным искажением данных (например, при ручном вводе номера карты). Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр, но не даёт возможности нахождения и исправления обнаруженной неточности.
Алгоритм разработан сотрудником фирмы IBM Хансом Питером Луном, описан в США в 1954 году, патент получен в 1960 году.
В настоящее время алгоритм является публичным достоянием. Рассмотрим его упрощённую версию.
Цифры проверяемой последовательности нумеруются слева направо, начиная с 1.
Цифры, оказавшиеся на чётных местах, остаются без изменений.
Цифры, стоящие на нечётных местах, умножаются на 2.
Если в результате такого умножения возникает число больше 9, оно заменяется суммой цифр получившегося произведения — однозначным числом, то есть цифрой.
Все полученные в результате преобразования цифры складываются. Если сумма кратна 10, то исходные данные верны.
По данному шестнадцатизначному числу n, определите, может ли оно являться корректным номером банковской карты?
Формат входных данных
Единственная строка входных данных содержит одно натуральное шестнадцатизначное число n.
Обратите внимание, что при заданных ограничениях для хранения данных необходимо использовать 64-битный тип данных, например longlong в C++, int64 в FreePascal, long в Java.
Формат выходных данных
Выведите Yes или No — ответ на вопрос задачи.
Ограничения
1015 ≤ n ≤ 1016 − 1
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере дано n = 4561261212345464
Первая цифра 4 стоит на нечётной позиции. Удваиваем её: 4 × 2 = 8. Результат не превышает 9.
Вторая цифра 5 стоит на чётной позиции. Не изменяем её.
Третья цифра 6 стоит на нечётной позиции. Удваиваем её: 6 × 2 = 12. Результат превышает 9, складываем цифры двузначного числа: 1 + 2 = 3.
Четвёртая цифра 1 стоит на чётной позиции. Не изменяем её.
...
Шестнадцатая цифра 4 стоит на чётной позиции. Не изменяем её.
Широко известна следующая математическая задача для младших школьников:
Вдоль стен квадратного бастиона требовалось поставить 16 часовых. Комендант разместил их так, как показано на рисунке слева, по 5 человек с каждой стороны.
Затем пришёл полковник и, недовольный размещением часовых, распорядился поставить солдат так, чтобы с каждой стороны их было по 6. Вслед за полковником пришёл генерал, рассердился на полковника за его распоряжение и разместил солдат по 7 человек с каждой стороны. Каково было размещение в двух последних случаях? Ответы на этот вопросы на рисунке по центру и справа.
Попробуйте решить обобщенную задачу: вдоль стен квадратного бастиона требовалось поставить n часовых, по k человек с каждой стороны. При этом количество часовых на всех углах бастиона должно быть одинаковым и количество часовых на всех его стенах тоже должно быть одинаковым. Удастся ли это сделать и каким образом?
Формат входных данных
Две строки входного файла содержат два натуральных числа: n и k.
Формат выходных данных
Выведите через пробел два неотрицательных целых числа — количество часовых на любом из углов и на любой из стен. Выведите -1, если часовых расставить нельзя.
Ограничения
1 ≤ k, n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснения к примерам
Первый пример соответствует случаю из условия.
Во втором примере часовых расставить требуемым образом невозможно.
В третьем примере требуемая расстановка приведена на рисунке ниже.
Сегодня Тимофей решил навести порядок в множестве натуральных чисел, рассортировав их по четырем столбикам. В первый столбик он записывал все числа, которые делятся на 6, во второй — оставшиеся числа, делящиеся на 2, в третий — оставшиеся числа, делящиеся на 3, в четвертый — все оставшиеся числа. На рисунке ниже вы можете видеть отсортированные по столбикам числа от 1 до 20.
Укажите четыре числа, которые будут расположены в n-й строке сверху.
Формат входных данных
Единственная строка входного файла содержит натуральное число n — порядковый номер строки.
Формат выходных данных
Выведите через пробел четыре натуральных числа, содержащихся в этой строке.
Ограничения
1 ≤ n ≤ 1015
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.
Долгое время шахматные партии игрались без контроля времени. Случалось, что игрок, имея заведомо проигрышную позицию или просто из «стратегических» соображений, брал соперника «на измор». Иногда это удавалось. Партии тянулись много часов подряд, сутками. На первом международном турнире 1851 года помощник судьи, фиксировавший ходы в партии Уильямс — Маклоу, сделал историческую запись: «Партия осталась неоконченной, поскольку оба противника заснули…» Еще один пример: в том же году Стаунтон, не выдержав медлительности своего противника Уильямсa, сдал матч при счете +6-2=3 в свою пользу, при том, что по регламенту матч игрался до 7 побед.
В наши дни, для того, чтобы фиксировать время, затрачиваемое игроками на обдумывание ходов используются специальные шахматные часы, а соревнования, в которых участникам дается мало времени, получают все большую популярность.
Так, блиц отличается от шахмат с обычным контролем времени тем, что от игрока требуется более быстрый расчёт вариантов, а также хорошая техника разыгрывания стандартных ситуаций, когда решающим фактором становится время. Популярность игры в блиц по 3 минуты и менее в режиме on-line обусловлена тем, что при таком контроле времени слабому шахматисту трудно незаметно пользоваться подсказками сильных шахматных программ, выиграть блиц у которых практически невозможно даже сильнейшим шахматистам. Обычно блиц применяется для выявления победителя, если шахматный матч между двумя примерно равными по силе шахматистами завершается вничью.
Однако как быть, если и блиц завершился вничью? В последние несколько лет в этом случае играется одна особая партия под названием «армагеддон». Вот ее краткие правила:
1) право выбора цвета фигур определяется жребием;
2) контроль времени: 5 минут белым и 4 минуты чёрным, с добавлением 3 секунд на ход каждому игроку, начиная с 61-го хода (это время добавляется ПЕРЕД очередным ходом);
3) в случае ничьей победителем объявляется шахматист, игравший чёрными фигурами. Таким образом, «армагеддон» всегда выявляет победителя, заканчивая соревнование.
Тимофей отвечает за техническое обеспечение шахматного матча. Помогите ему написать программу, определяющую, сколько секунд осталось в запасе у игрока при игре «армагеддон».
Формат входных данных
Первая строка входного файла содержит символ: W или B — цвет фигур игрока. Вторая строка содержит натуральное число n — количество сделанных игроком ходов. Третья строка содержит n натуральных чисел ti, записанных через пробел — время в секундах, затраченное на i-й ход.
Формат выходных данных
Выведите одно неотрицательное целое число — количество оставшихся на очередной ход секунд. Если данные содержат ошибку (например, в случае, когда время на очередной ход превышало максимально допустимое, а игра не завершилась) — выведите число -1.
Ограничения
1 ≤ n ≤ 100
1 ≤ ti ≤ 1000
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 59, получат не менее 40 баллов.
Пояснение к примеру
В примере игрок белыми фигурами сделал 3 хода, суммарно затратив 90 секунд. Из 5 минут на оставшиеся ходы у него осталось 210 секунд.
