Ох уж эти уроки математики... Сегодня учитель Владимир Яковлевич развлекался игрой в "Тройки". Он записывал на доске натуральное число, состоящее из одних троек, и требовал, чтобы класс ответил на вопрос, какая цифра находится на k-ой позиции в квадрате этого числа. Пока никто не пострадал от гнева Владимира Яковлевича, напишите программу, находящую ответ на этот вопрос.
Формат входных данных
В единственной строке входного файла через пробел записаны два натуральных числа: n – длина числа, состоящего из одних троек и k - интересующая учителя позиция в квадрате числа. Гарантируется, что k не превосходит длину получившегося квадрата числа.
Недавно отечественные историки обнаружили неизвестную ранее берестяную грамоту, на которой, ко всеобщему удивлению, описывалась финальная игра 1520 года по снежкам между сборными Москвы и Новгорода. К сожалению, сведения оказались частично утраченными, но кое-что удалось разобрать.
В верхней части грамоты описывались правила игры. В снежки играют две команды, друг против друга, в составе каждой ровно k игроков. Игрок, до которого дошла очередь бросать, старается попасть снежком в любого из соперников, если это удается - команда получает одно очко. После этого ход переходит к соперникам. Игра заканчивается победой команды, первой набравшей заранее обговоренное количество очков.
В нижней части грамоты содержалась информация о финальной игре сезона. Оказалось, что две команды в сумме сумели набрать n очков, что в составе сборной Москвы лучшим снайпером оказался Иван Иванов (это значит, что любой другой участник его команды набрал строго меньше очков в финале), а самым метким новгородцем стал Петр Петров (по тем же критериям).
Помогите историкам! Определите количество возможных результатов финальной игры.
Формат входных данных
В единственной строке через пробел записаны четыре натуральных числа k, n, a и b - количество участников в каждой команде, сумма набранных очков, количество очков Иванова и Петрова соответственно. Гарантируется непротиворечивость входных данных.
Формат выходных данных
Выведете одно натуральное число - ответ на задачу.
Ограничения
1 ≤ k ≤ 100
1 ≤ n, a, b ≤ 1015
a + b ≤ n
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: 1 ≤ n ≤ 100, баллы: 20.
Подзадача 2: 1 ≤ n ≤ 105, баллы: 30.
Подзадача 3: нет дополнительных ограничений, баллы: 50.
Пояснения к примерам
Комментарий к первому примеру: единственный счет, удовлетворяющий всем условиям, это 3:1. Иванов набрал два очка, второй участник сборной Москвы принес одно очко, третий не попал ни разу. У новгородцев отличился только Петров.
Комментарий ко второму примеру: игра могла завершиться со счетом 7:13, 8:12, 9:11 или 11:9. Ничья невозможна.
На региональном этапе Всероссийской олимпиады школьников по обществознанию участникам предлагалась следующая задача: "На столе лежат четыре карты. Известно, что с одной стороны на них написаны цифры, а с другой — рубашка синего (С) или красного (К) цвета. Карты такие: К, С, 6, 3. Какие карты необходимо и достаточно перевернуть, чтобы проверить правило «Если с одной стороны нечетное число, то с другой — синяя рубашка»"?
Решите обобщенную задачу. По предложенному списку карт, определите количество карт, которое необходимо и достаточно перевернуть, чтобы проверить определенное правило, идентичное вышеописанному, в котором могут быть изменены два слова - четность числа и цвет рубашки.
Формат входных данных
Первая строка входного файла содержит одно натуральное число n - количество карт на столе. Во второй строке через пробел содержится описание этих карт в следующем формате: если карта лежит рубашкой вверх, то она кодируется цветом рубашки: символ "b" соответствует синему цвету, "r" - красному. Если же карта лежит вверх числом, то записано само это число x. В третьей строке дано описание правила, которое нужно проверить - четность числа (число 0 соответствует слову "четное", 1 - "нечетное") и цвет рубашки ("b" или "r").
Формат выходных данных
Выведите одно неотрицательное целое число - ответ на задачу.
Ограничения
1 ≤ n ≤ 100
2 ≤ x ≤ 9
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n = 1, получат не менее 10 баллов.
Решения, верно работающие при n = 2, получат не менее 20 баллов.
Пояснение к примеру
Пример соответствует заданию из условия задачи. Дано 4 карты. Зашифровано правило «Если с одной стороны нечетное число, то с другой — синяя рубашка».
Назовем число плавным, если его две соседние цифры различаются не более, чем на 1. Например, числа 7, 1011, 2345 или 2323455665 - плавные, а 13, 90 или 102 - нет.
Назовем число оригинальным, если оно обладает следующим свойством: первые k цифр этого числа образуют число, делящееся на k для любого 1 ≤ k ≤ длиначисла. Например, число 3216 - оригинальное. Действительно: 3 делится на 1, 32 делится на 2, 321 делится на 3, 3216 делится на 4.
Найдите n-е по счету число, которое одновременно является и плавным, и оригинальным.
Формат входных данных
Единственная строка входного файла содержит одно натуральное число n.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу.
Тимофей очень любит числа, являющиеся точными степенями двойки и тройки. У него даже есть два альбома, в которых хранятся карточки с этими числами: в первом можно найти 1, 2, 4, 8, 16 и так далее, а во втором — 1, 3, 9, 27 и так далее.
Тимофей хочет подарить папе число n, составленное из суммы чисел на этих карточках. Поскольку ему жалко расставаться со своими числами, он хочет подарить папе наименьшее число своих карточек, числа на которых в сумме дают n. Сколько карточек Тимофей подарит папе?
Формат входных данных
Единственная строка входного файла содержит одно натуральное число n.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу.
Ограничения
1 ≤ n ≤ 105
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 100, получат не менее 40 баллов.
Пояснения к примерам
В первом примере число два можно составить двумя способами: 1 + 1 или 2. Тимофей выберет второй способ и передаст папе одну карточку с двойкой.
Во втором примере есть способ (не единственный) представить число 79 в виде набора из четырех карточек: 79 = 64 + 9 + 4 + 2. Меньшим набором карточек обойтись нельзя.
Тимофей с друзьями занят разработкой новой масштабной многопользовательской онлайн-игры "Мир и война". Процедурно генерируемый открытый мир, обстановка позднего средневековья, магия и экономика, балы и сражения, драконы и странствующие монахи, университеты и гильдии воров, строительство замков и меняющаяся погода - фантазия разработчиков не знает границ.
Прямо сейчас Тимофей разрабатывает алгоритмы мирной профессии пряжник. Как несложно догадаться, этот работник будет изготавливать пряжки для ремней и поясов из прямоугольных металлических заготовок размером a × b. Пряжка представляет собой рамку шириной 1 с двумя одинаковыми прорезями наибольшей площади, расстояние между которыми равно 1 при нечетной ширине пластины или 2 при четной ширине.
Когда пряжник вырезает из заготовки два металлических прямоугольника, у него в руках оказывается еще две заготовки, из которых (если размеры позволяют) можно сделать новые пряжки меньшего размера! В конце-концов у пряжника останутся маленькие заготовки, которые уже ни на что не годны. Тимофей, прежде чем придумать, как их ещё можно использовать, хочет узнать их минимально возможную общую площадь.
Формат входных данных
Единственная строка входного файла содержит два натуральных числа, записанных через пробел: a и b.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу.
Ограничения
1 ≤ a, b ≤ 104
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере рассмотрен случай минимально возможной заготовки, из которой можно сделать пряжку с двумя единичными по площади отверстиями.
Во втором примере заготовка сразу идет в отходы, её размеры слишком малы.
Во третьем примере пряжник может добиться такого выбора направления пряжек, чтобы минимизировать общую площадь отходов до 8. При других вариантах его работы ответ будет существенно больше.
2020 год оказался насыщенным интересными и драматичными событиями. Но с точки зрения математики он забавен тем, что в течение этого года встречались даты, для записи которых можно использовать ровно две различные цифры (например, 20.02.2020). Для предложенной такой даты, определите ближайшую будущую, обладающую тем же свойством.
Формат входных данных
Единственная строка входного файла содержит описание даты: число, месяц и год - три натуральных числа в формате dd.mm.year, разделенных символом "точка". Число и месяц записаны в формате с ведущим нулем, год - натуральное число. Гарантируется, что среди цифр даты ровно две различные. Гарантируется корректность даты (соответствует текущим правилам построения календаря).
Формат выходных данных
Выведите в том же формате ближайшую будущую дату, в записи которой используются НЕ БОЛЕЕ двух данных цифр.
