Задача A. СНИЛС ≡

Условие

Страховой номер индивидуального лицевого счёта страхового свидетельства обязательного пенсионного страхования (он же СНИЛС) проверяется на корректность контрольным числом. СНИЛС имеет вид: «XXX-XXX-XXX YY», где XXX-XXX-XXX — собственно номер, а YY — контрольное число.

Контрольное число СНИЛС рассчитывается следующим образом:

1) Каждая цифра СНИЛС умножается на номер своей позиции (позиции отсчитываются с конца, то есть, справа).

2) Полученные произведения суммируются.

3) Если сумма меньше 100, то контрольное число равно самой сумме, а если равна 100 или 101, то контрольное число равно 00.

4) Если сумма больше 101, то сумма делится по остатку на 101 и контрольное число определяется остатком от деления аналогично предыдущему пункту.

Для указанного номера СНИЛС определите его контрольное число.

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

Единственная строка входного файла содержит девять десятичных цифр n — номер СНИЛС.

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

Выведите две десятичных цифры — контрольное число для этого номера СНИЛС.

Ограничения

000000000 ≤ n ≤ 999999999

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

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

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

116973385

89

999999999

01

Задача B. Две параболы ≡

Условие

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

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

В первой строке через пробел записаны три целых числа — коэффициенты первой квадратичной функции a₁, b₁ и c₁, во второй строке в том же формате записаны коэффициенты второй квадратичной функции a₂, b₂ и c₂.

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

Выведите "Yes" или "No" (без кавычек) — ответ на вопрос задачи.

Ограничения

 − 1000 ≤ a₁, b₁, c₁, a₂, b₂, c₂ ≤ 1000

a₁ ≠ 0

a₂ ≠ 0

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

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

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

Смотри рисунок.

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

2 -3 -4
-1 2 5

Yes

2 -3 -2
1 -2 -4

No

Задача C. Квадраты в прямоугольнике ≡

Условие

Перед Тимофеем стоит серьёзная математическая задача — определить количество различных квадратов в прямоугольнике размером a на b.

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

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

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

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

Ограничения

1 ≤ a, b ≤ 10⁶

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

Баллы за задачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 1: a = 1, баллы: 10.

Подзадача 2: a = 2, баллы: 10.

Подзадача 3: 1 ≤ a, b ≤ 1000, баллы: 20.

Подзадача 4: нет дополнительных ограничений, баллы: 60.

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

Комментарий к первому примеру:

Прямоугольник вмещает 5 квадратов со стороной один.

Комментарий ко второму примеру:

Прямоугольник вмещает 12 квадратов со стороной один, 6 квадратов со стороной два и 2 квадрата со стороной три. Всего 20 различных квадратов.

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

1 5

5

4 3

20

Задача D. Лотерея Амидакудзи ≡

Условие

Амидакудзи (яп. «лотерея Амиды») — японский метод лотереи, позволяющий быстро распределить некоторые предметы между её участниками. Амидакудзи используется, чтобы распределить вещи среди людей, когда количество распределяемых вещей равно числу людей. Например, работа по дому или призы могут быть справедливо и случайным образом распределены при помощи такой лотереи.

Амидакудзи состоит из так называемых «лесенок», в которых число вертикальных линий равно числу участников и вещей, а горизонтальные располагаются в случайном порядке.

Правила игры: необходимо выбрать линию в верхней части и следовать за этой линией вниз. При столкновении с горизонтальной нужно повернуть на соседнюю линию и следовать уже по ней. Таким образом нужно следовать вниз, пока линии не кончатся. Под линиями обозначены различные «призы», которые достигшие нижнего уровня и получают.

Определите, какую вертикальную линию следует выбрать, чтобы получить приз под порядковым номером x?

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n — количество вертикальных линий и k — количество горизонтальных линий. Во второй строке через пробел расположено k натуральных чисел a_i — описание горизонтальных линий, перечисленных в порядке сверху вниз (все линии расположены на разной высоте). Если a_i = p, это значит, что горизонтальная линия соединяет вертикальные линии под номерами p и p + 1. В третьей строке расположено натуральное число x — выбранный участником номер приза.

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

Выведите одно натуральное число — порядковый номер вертикальной линии, которую следует выбрать участнику.

Ограничения

1 ≤ x ≤ n ≤ 10⁵

1 ≤ k ≤ 10⁵

1 ≤ a_i ≤ n − 1

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

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

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

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

Смотри рисунок. В примере дано n = 7 вертикальных линий и k = 9 горизонтальных линий. Участник, выбравший четвертую вертикальную линию пройдет по маршруту красной линии и получит приз под пятым номером.

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

7 9
3 1 2 4 6 5 2 3 4
5

4

Задача E. Простая сумма ≡

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

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

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

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

18

99