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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

000000000 ≤ n ≤ 999999999

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

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

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

Стандартный вход Стандартный выход
1
116973385
89
2
999999999
01

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

В первой строке через пробел записаны три целых числа — коэффициенты первой квадратичной функции a1, b1 и c1, во второй строке в том же формате записаны коэффициенты второй квадратичной функции a2, b2 и c2.

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

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

Ограничения

 − 1000 ≤ a1, b1, c1, a2, b2, c2 ≤ 1000

a1 ≠ 0

a2 ≠ 0

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

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

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

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

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

Стандартный вход Стандартный выход
1
2 -3 -4
-1 2 5
Yes
2
2 -3 -2
1 -2 -4
No

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

Ограничения

1 ≤ a, b ≤ 106

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

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

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

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
1 5
5
2
4 3
20

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ x ≤ n ≤ 105

1 ≤ k ≤ 105

1 ≤ ai ≤ n − 1

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
7 9
3 1 2 4 6 5 2 3 4
5
4

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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

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

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

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

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

Стандартный вход Стандартный выход
1
18
99

0.555s 0.022s 31