В магазине "Программист-спортсмен" большая распродажа! В преддверии поступления товаров нового сезона, нужно срочно освободить полки и витрины, продавая прошлогодние коллекции по бросовым ценам. К сожалению, установить произвольную цену на товар нельзя, в соответствии с антимонопольным законом на распродажу распространяются следующие условия:
1) На товар можно установить любую скидку (от 1 до 99 процентов) по сравнению с ценой товара в предыдущий день.
2) И скидка, и новая стоимость товара должны являться натуральными числами.
Например, если товар стоит 20 рублей, на него можно установить скидку 25% и на следующий день этот товар будет продаваться по 15 рублей. А вот скидку в 30% установить нельзя — новая цена будет выражаться дробным числом рублей.
Молодой программист Тимофей каждый день после работы заходит в магазин и скупает все товары, которые сегодня стоят 1 рубль. Как скоро хозяину магазина удастся снизить стоимость товара с n рублей до 1 рубля?
Формат входных данных
Единственная строка входных данных содержит натуральное число n — начальная стоимость товара в рублях. Гарантируется, что это значение таково, что существует последовательность корректных скидок, снижающих стоимость товара до 1 рубля.
Формат выходных данных
Выведите одно натуральное число — наименьшее количество дней, необходимых для максимального снижения стоимости товара.
Ограничения
2 ≤ n ≤ 1018
Пояснение к примеру
В примере дана начальная стоимость товара 125 рублей. В первый день на него устанавливается скидка 96% и товар продается по цене 5 рублей. Во второй день скидка составит 80% и вечером товар будет куплен Тимофеем за 1 рубль.
Две подруги, Нина и Марина, живут квартирах n и m в одном подъезде самого длинного дома в мире. Каким может быть наибольший номер этого подъезда? Количество квартир в каждом подъезде одинаково.
Формат входных данных
Две строки входных данных содержит два натуральных числа n и m.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Ограничения
1 ≤ m < n ≤ 109
Пояснение к примеру
В примере дано n = 52 и m = 41. Эти квартиры могут находиться в первом подъезде (если в одном подъезде квартир не меньше, чем 52).
Эти квартиры могут находиться во втором подъезде (если в одном подъезде квартир не меньше, чем 26 и не больше, чем 40).
Эти квартиры могут находиться в третьем подъезде (если в одном подъезде квартир не меньше, чем 18 и не больше, чем 20).
Эти квартиры могут находиться в четвертом подъезде (если в одном подъезде ровно 13 квартир).
Эти квартиры не могут находиться в подъезде с номером большим, чем 4. Ответ на вопрос задачи — 4.
Тимофей с друзьями придумывает новую настольную игру. Поле для игры представляет собой треугольник со стороной n, разбитый на единичные треугольники со стороной 1. В случайном месте поля будет расположена запретная зона (тоже в форме треугольника, полностью накрывающая конечное число единичных треугольников) со стороной m, внутри которой нет никаких линий. Помогите Тимофею определить длину всех линий игрового поля.
Формат входных данных
Первая строка входных данных содержит два натуральных числа,
записанных через пробел: n и m.
Формат выходных данных
Выведите одно натуральное число — ответ на задачу.
На обычной шахматной доске 8 × 8 находится один белый конь и несколько черных ферзей. Конь может перемещаться по обычным правилам, но не может занять поле, если на нём находится ферзь или оно находится под боем ферзя. На скольких полях сможет побывать конь?
Формат входных данных
Первая строка входных данных содержит одно натуральное число n — количество фигур на доске. Во второй строке через пробел приведено n двузначных чисел — координаты фигур. Первые n − 1 чисел соответствуют расстановке ферзей, последнее — коня. Первая цифра числа — номер вертикали, вторая — горизонтали шахматного поля. Гарантируется, что координаты всех фигур различны. Гарантируется, что конь в начальном расположении не находится под боем.
Формат выходных данных
Выведите одно натуральное число — количество различных полей шахматного поля, до которых может добраться конь (включая исходное).
Ограничения
2 ≤ n ≤ 10
Пояснение к примеру
Смотри рисунок. Начальное положение фигур слева. Справа красными значками отмечены поля, находящиеся под боем ферзей. Зелеными значками отмечены поля, до которых конь может добраться. Вместе с исходным полем, всего их пять.
На обычной шахматной доске 8 × 8 находится один белый конь и несколько черных ферзей. Конь может перемещаться по обычным правилам, но не может занять поле, если оно находится под боем ферзя. Однако, он может "съесть" ферзя, при условии, что тот не находится под защитой другого ферзя, получив, таким образом, дополнительные поля для перемещения (при этом, у него сохраняется возможность "съесть" ещё какого-нибудь ферзя). Теоретически, если ферзи не защищают друг друга, конь может съесть их всех и без помех "гулять" по всей шахматной доске. На скольких полях сможет побывать конь при данной расстановке?
Формат входных данных
Первая строка входных данных содержит одно натуральное число n — количество фигур на доске. Во второй строке через пробел приведено n двузначных чисел — координаты фигур. Первые n − 1 чисел соответствуют расстановке ферзей, последнее — коня. Первая цифра числа — номер вертикали, вторая — горизонтали шахматного поля. Гарантируется, что координаты всех фигур различны. Гарантируется, что конь в начальном расположении не находится под боем.
Формат выходных данных
Выведите одно натуральное число — количество различных полей шахматного поля, до которых может добраться конь (включая исходное).
Ограничения
3 ≤ n ≤ 10
Пояснение к примеру
Смотри рисунок. Начальное положение фигур слева. Два ферзя на полях 15 и 48 защищают друг друга, съесть их нельзя, также нельзя перемещаться на те поля, которые находятся под их боем. Ферзь на поле 83 может быть съеден конем первым же ходом. Справа красными значками отмечены поля, находящиеся под боем ферзей, которых конь не сможет съесть. Зелеными значками отмечены поля, до которых конь может добраться. Вместе с исходным полем, всего их 24.
В первом "Д" классе ажиотаж. Все ученики играют в популярную, увлекательную и неувядающую игру — "Морской бой". Но поскольку ребята еще маленькие и считать умеют с трудом (да и перемены короткие) — в классические правила внесен ряд упрощений.
Игровое поле — прямоугольник размером 1 х n. На этом поле каждый участник размещает a «однопалубных» и b «двухпалубных» кораблей. При размещении корабли не могут касаться друг друга сторонами. На рисунке приведен один из вариантов размещения кораблей при n = 10, a = 2 и b = 2.
Первоклассник Тимофей хочет создать собственную стратегию начальной расстановки флота. Для начала ему необходимо выяснить — сколько существует различных расстановок для конкретной тройки значений n, a и b. Поскольку Вы в глазах Тимофея — непререкаемый авторитет в области программирования, за помощью будущий стратег обратился к Вам.
Формат входных данных
В единственной строке входных данных через пробел записаны три целых числа n, a и b — размер поля и начальные количества кораблей размером в одну и две клетки соответственно.
Формат выходных данных
Выведите одно целое число — количество различных вариантов размещения кораблей. Гарантируется, что ответ на задачу при любых входных данных не превосходит 1012.
Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно. Найдите наименьшее натуральное число, факториал которого делится нацело на 2m.
Формат входных данных
Единственная строка входных данных содержит натуральное число m.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи. Гарантируется, что ответ не превысит 109.
Ограничения
1 ≤ m ≤ 109
Пояснение к примеру
В примере нужно найти наименьшее число, факториал которого делится нацело на 210 или 1024. Перебирая все числа в порядке возрастания, находим, что 12! = 479001600 разделится на 1024 без остатка.
Натуральный ряд записали змейкой в виде треугольника. Найдите сумму чисел, стоящих на сторонах числового квадрата с вершиной в единице и двумя сторонами, лежащими на сторонах треугольника. Поскольку ответ может оказаться очень большим, выведите его последнюю цифру.
Формат входных данных
Единственная строка входных данных содержит натуральное число n — длину стороны квадрата.
Формат выходных данных
Выведите одну десятичную цифру — ответ на задачу.
Ограничения
1 ≤ n ≤ 1018
Пояснение к третьему примеру
В примере дано n = 4. Сумма чисел 1 + 2 + 4 + 5 + 9 + 10 + 16 + 19 + 23 + 30 + 32 + 43 = 194. Последняя цифра — 4.
На днях в Логландии прошла вселогландская олимпиада школьников по математике. Мальчик Влад не смог пройти на заключительный этап этой олимпиады, но его очень заинтересовала одна задача c финала. Суть данной задачи следующая: дан отрезок целых чисел от 1 до n, необходимо определить количество различных чисел, которое можно представить в виде суммы одной или более неповторяющихся степеней k (т. е. чисел k1, k2, k3 и т. д.)
Формат входных данных
В первой строке входных данных записано два целых числа n и k.
Формат выходных данных
Выведите одно число — количество различных чисел от 1 до n, которое можно представить в указанном виде.
Ограничения
1 ≤ n ≤ 1018
1 ≤ k ≤ 20
Пояснение к примерам
В первом примере мы может образовать из чисел 1, 3, 9, 27 следующие варианты: 1, 3, 4, 9, 10, 12, 13, 27, 28, 30.
Во втором примере мы можем представить все числа от 1 до 7.
