Задача A. Двоичная сумма ≡

Условие

Однажды на уроке информатики Тимофею нужно было сложить два натуральных двоичных числа одинаковой длины n. У первого из чисел в начале располагались a единиц, а остальные цифры были нули. У второго числа в начале располагались b единиц, а остальные цифры были нули. Сколько нулей и единиц будет в сумме этих чисел?

Формат входных данных

Три строки входного файла содержат натуральные числа: n, a и b.

textbfОбратитевнимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например textbflong textbflong в textbfC +  + , textbfint 64 в textbfFree textbfPascal, textbflong в textbfJava.

Формат выходных данных

Выведите через пробел два натуральных числа — количество нулей и единиц в сумме исходных чисел.

Ограничения

1 ≤ a ≤ b ≤ n ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10, получат не менее 40 баллов.

Пояснение к примеру

В примере дано n = 4, a = 2 и b = 3. Складываются два четырехзначных двоичных числа 1100 и 1110. Найдем их сумму: 1100₂ + 1110₂ = 12₁₀ + 14₁₀ = 26₁₀ = 11010₂. В сумме 2 нуля и 3 единицы.

Примеры тестов

4
2
3

2 3

Задача B. Причудливое блуждание ≡

Условие

Как-то раз Тимофей сидел на контрольной работе по математике. И свой вариант, и вариант соседки по парте, красавицы Алёны, давно были решены. От скуки Тимофей стал рисовать на клетчатом листочке-черновике.

Из центра координатной плоскости Тимофей начинает рисовать отрезки так, как указано на рисунке. Какова будет длина всех нарисованных им отрезков, когда он доберется до точки с координатами (x, y)?

Формат входных данных

Единственная строка входного файла содержит два целых числа, записанных через пробел: x и y — координаты точки.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на задачу.

Ограничения

0 ≤ x, y ≤ 10⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Примеры тестов

3 6

39

Задача C. Вычеркивание чисел ≡

Условие

В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его сотрудники открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать.

Сегодня Тимофею ничего научного не приходит в голову. Чтобы окружающие не заподозрили его в бездеятельности, он вычеркивает некоторые числа из бесконечного ряда натуральных чисел. Делает он это, впрочем, не хаотично, а по определенным правилам.

На первом шаге он вычеркнул каждое второе натуральное число. На втором шаге из оставшихся чисел он вычеркнул каждое третье число. На третьем шаге из оставшихся чисел он вычеркнул каждое четвертое число, и так далее.

Попробуйте определить, на каком шаге Тимофей вычеркнет своё любимое число n.

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно натуральное число — на каком шаге будет вычеркнуто число n. Если оно не будет вычеркнуто никогда, выведите число -1.

Ограничения

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10⁶, получат не менее 60 баллов.

Пояснение к примерам

В первом примере n = 15. Исходный ряд натуральных чисел:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...

После первого шага Тимофей вычеркнет каждое второе число, то есть останутся только нечетные числа:

1 3 5 7 9 11 13 15 17 19 21 ...

После второго шага Тимофей вычеркнет каждое третье оставшееся число:

1 3 7 9 13 15 19 21 ...

После третьего шага Тимофей вычеркнет каждое четвертое оставшееся число:

1 3 7 13 15 19 ...

После четвертого шага Тимофей вычеркнет каждое пятое оставшееся число:

1 3 7 13 19 ...

Любимое число вычеркнуто на четвертом ходу.

Во втором примере n = 19. Оно не будет вычеркнуто никогда: после четвертого шага будут вычеркиваться только числа, больше, чем 19.

Примеры тестов

15

4

19

-1

Задача D. Сумма цифр числа ≡

Условие

Найдите количество натуральных чисел длины d, сумма цифр которых равна n.

Формат входных данных

Единственная строка входного файла содержит два натуральных числа, записанных через пробел: d и n.

Формат выходных данных

Выведите одно натуральное число — ответ на задачу. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

1 ≤ d ≤ 19

1 ≤ n ≤ 9 × d

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере нужно найти количество трехзначных чисел с суммой цифр 4. Это 103, 112, 121, 130, 202, 211, 220, 301, 310 и 400 — всего 10 чисел.

Примеры тестов

3 4

10

Задача E. Дубль ≡

Условие

Стандартный набор традиционного домино включает в себя 28 костяшек. Костяшка домино представляет собой прямоугольную плитку, длина которой вдвое больше ширины. Её лицевая сторона разделена линией на две квадратные части. Каждая часть содержит от нуля до шести точек. В полном наборе представлены все комбинации пар от 0 до наибольшего количества точек на каждой из половинок костяшки. В специализированных наборах домино возможное количество точек может доходить до девяти, двенадцати, пятнадцати, восемнадцати или быть произвольным. Например, полный набор костяшек при максимальном числе точек равным 3 будет таким: 0-0, 0-1, 0-2, 0-3, 1-1, 1-2, 1-3, 2-2, 2-3, 3-3.

Игрок вытаскивает из полного набора домино с максимальным числом точек n одну костяшку. Какова вероятность, что числа на половинках плиток будут одинаковыми (дубль)?

Формат входных данных

Единственная строка входного файла содержит целое неотрицательное число n.

Формат выходных данных

Выведите два неотрицательных целых числа — числитель и знаменатель несократимой дроби, выражающей вероятность описываемого события.

Ограничения

0 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере n = 6 (соответствует обычному комплекту домино из 28 костяшек). Всего дублей в комплекте 7.

Напомним, что вероятностью наступления события называется отношение числа благоприятных исходов к общему числу исходов. В нашем случае есть 7 благоприятных исходов (дублей) из 28 общих (всех костяшек). 728 = 14.

Примеры тестов

6

1 4