Задача 1A. Сумма ≡

Условие

Заданы два целых числа: a и b. Требуется написать программу, которая вычисляет их сумму.

Формат входного файла

Входной файл содержит разделенные пробелом целые числа a и b.

Формат выходного файла

Выходной файл должен содержать одно число — сумму чисел a и b.

Ограничения

1 ≤ a ≤ b ≤ 10⁹

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

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

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

2 3

5

Задача 1B. Неделящиеся числа ≡

Условие

Найдите n-е по счету натуральное число, которое не делится на d.

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁹

2 ≤ d ≤ 10⁹

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

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

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

В примере нужно найти пятое число, которое не делится на 3. Вычеркнув из ряда натуральных чисел те, которые делятся на 3, получим: 1, 2, 4, 5, 7, ...

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

5 3

7

Задача 2A. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

Поэтому им хотелось бы иметь компьютерную программу, принимающую на вход текущее время (часы и минуты) и вычисляющую, сколько времени осталось до Нового года.

Число секунд в текущем времени принять равным 0.

Формат входного файла

Входной файл содержит текущее время — часы и минуты.

Формат выходного файла

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

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

12 0

12 0

23 59

0 1

22 25

1 35

Задача 2B. Сложение массива чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

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

3
1 2 3

6

Задача 2C. Максимум в массиве ≡

Условие

Вводится массив, состоящий из целых чисел. Найти наибольшее среди них

Формат входного файла

Сначала задано число N — количество элементов в массиве (1 ≤ N ≤ 35). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел в диапазоне от  − 2³¹ до 2³¹ − 1.

Формат выходного файла

Необходимо вывести значение наибольшего элемента в массиве.

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

3
1 2 3

3

Задача 2D. Ксюша и массив ≡

Условие

Ксюша — начинающий программист. Сегодня она знакомится с массивами. У нее есть массив a₁, a₂, …, a_n, состоящий из n целых положительных чисел. Преподаватель в университете задал ей задачу. Найти такое число в массиве, на которое делятся все элементы массива. Помогите ей, найдите это число!

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

В первой строке вводится целое число n (1 ≤ n ≤ 10⁵) — количество элементов в массиве. В следующей строке через пробел содержатся целые числа a₁, a₂, …, a_n(1 ≤ a_i ≤ 10⁹) — элементы массива.

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

Выведите единственное целое число — число из массива, на которое делятся все элементы массива. Если такого числа нет, выведите  − 1.

Если существует несколько ответов, разрешается вывести любой.

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

3
2 2 4

2

5
2 1 3 1 6

1

3
2 3 5

-1

Задача 2E. Массив наоборот ≡

Условие

Во входном файле дан массив целых чисел a₁, a₂, ..., a_N. Требуется вывести этот массив в обратном порядке.

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

Формат выходного файла

Выходной файл должен содержать N чисел — массив a_i, записанный в обратном порядке.

Ограничения

1 ≤ N ≤ 100000

 − 10⁹ ≤ a_i ≤ 10⁹

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

4
1 2 3 4

4 3 2 1

6
9 1 3 -2 3 5

5 3 -2 3 1 9

Задача 2F. Количество каждой цифры ≡

Условие

Петя написал на заборе N цифр. Когда Вася увидел то, что натворил Петя, он решил посчитать, сколько раз написана каждая цифра.

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел (цифр), разделённых пробелами.

Формат выходного файла

Выходной файл должен содержать 10 чисел — количество цифр 1, количество цифр 2, и т.д., количество цифр 9, количество цифр 0.

Ограничения

1 ≤ N ≤ 1000000

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

4
1 2 1 0

2 1 0 0 0 0 0 0 0 1

7
9 1 3 2 3 2 7

1 2 2 0 0 0 1 0 1 0

Задача 3A. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

Формат входного файла

Входной файл содержит три целых числа: W, H, N

Формат выходного файла

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Задача 3B. Гаджет в кредит ≡

Условие

Студент Вася решил приобрести себе новый гаджет. Стипендия у Васи небольшая, а гаджет — дорогой, поэтому Вася решил купить гаджет в кредит.

В магазине Васе объяснили правила предоставления кредита.

• Первоначально сумма долга равна стоимости гаджета C.
• По истечении максимум N лет вся сумма долга должна быть выплачена
• Вася должен определить ежемесячный платеж M — целое число рублей, которое он будет выплачивать каждый месяц. Исключение может составлять последний платёж — оставшаяся на последний месяц сумма долга может оказаться меньше M.
• Каждый месяц после Васиного платежа оставшаяся сумма долга увеличивается на P процентов и округляется вверх до целого числа.

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

Рекомендуется рассмотреть частичные решения

1. P = 0
2. C, P ≤ 10³

Формат входного файла

Входной файла содержит целые числа N P C.

Формат выходного файла

Выходной файл должен содержать единственное целое число — подходящий Васе ежемесячный платеж.

Ограничения

1 ≤ C ≤ 10⁹; 0 ≤ P ≤ 10⁹; 1 ≤ N ≤ 10⁴

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

1 0 1

1

1 124 12

8

1 1 12

2

Задача 3C. Паркет ≡

Условие

Андрей укладывает дома пол. У него длинный коридор длиной L.

У Андрея есть бесконечное количество досок, длины которых равны d. Необходимо полностью уложить пол досками. Доски можно пилить, но при этом в укладке нельзя использовать части досок короче c.

Сколько досок Андрею необходимо разрезать, чтобы уложить пол?

Формат входного файла

Входные данные содержат три целых числа: L, d, c.

Формат выходного файла

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

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

Ограничения

1 ≤ L, d ≤ 10⁹

0 ≤ c ≤ 10⁹

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

10 2 2

0

10 3 2

2

100 9 9

-1

Задача 3D. Безопасная поездка ≡

Условие

Вам требуется успеть на важную встречу. Сейчас вы находитесь в точке 0, встреча пройдёт в точке с координатой D метров через T секунд. Но есть ещё одна проблема: светофоры.

Начиная с момента 0, светофор с номером i сначала показывает красный свет в течение a_i секунд, затем зелёный в течение b_i секунд, а затем процесс повторяется. В момент смены сигнала считается, что продолжает гореть предыдущий сигнал.

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

Формат входного файла

В первой строке записаны целые числа T, D и N "--- время до встречи, координата места встречи и число светофоров (1 ≤ T ≤ 10⁹, 1 ≤ D ≤ 10⁹, 0 ≤ N ≤ 50).

В следующих N строках записано по три целых числа a_i, b_i, p_i "--- длительность красного и зелёного сигналов i-го светофора и его положение на пути до встречи (1 ≤ a_i, b_i ≤ 10⁹, 1 ≤ p_i ≤ 10⁹). Позиции светофоров не совпадают, в точке D светофора нет.

Формат выходного файла

Выведите единственное целое число "--- минимальную скорость. Абсолютная или относительная погрешность не должна превышать 10^− 5. Если добраться вовремя невозможно, выведите  − 1.0.

Ограничения

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

10 10 1
3 4 3

1.0

12 16 2
2 3 2
3 2 9

1.7500000000000004

12 13 5
1 2 3
2 2 5
3 3 7
1 6 9
3 4 11

1.25

Задача 4A. Слово из кубиков ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

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

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Задача 4B. Числовые ребусы ≡

Условие

Однажды юному программисту Серёже попалась книга с головоломками. Ему особенно понравилось решать числовые ребусы. Он решил большое количество ребусов, но иногда у него получались ответы, не совпадающие с ответами в книге. Поэтому Серёже очень пригодилась бы программа, вычисляющая все возможные ответы к данному числовому ребусу.

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

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

Во 2-м примере должно быть написано 2014 + ГОД = СОЧИ, но из-за того, что русские буквы в примерах не отображаются, они были заменены на другие буквы.

Формат входного файла

Входной файл содержит 3 строки, представляющие собой числа, в которых некоторые цифры заменены на не цифровые символы с ASCII-кодом больше 32.

Формат выходного файла

Выходной файл должен содержать все возможные ответы на ребус в произвольном порядке, по одному в каждых 3-х строках, ответы нужно разделять пустыми строками.

Выводить следует те ответы, в которых нет незначащих нулей в начале чисел.

Ограничения

Количество символов в каждом числе во входном файле не превосходит 9.

Общее количество не цифровых символов во всех числах находится в пределах от 1 до 6.

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

drama
drama
teatr

18969
18969
37938

2014
AOB
CODE

2014
789
2803

2014
891
2905

2014
893
2907

2014
896
2910

OXOXO
AXAXA
AXAXAX

90909
10101
101010

2A14
AAB
AODE

2214
221
2435

2214
225
2439

Задача AA. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел a_i.

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

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

3
1 1 2

1 2 3

2
2 5

-1

Задача AB. Быки и коровы 2 ≡

Условие

На одномерном поле длиной N клеток пасутся быки и коровы. Каждая клетка либо пустая, либо занята быком, либо занята коровой.

На поле периодически нападают волки, поэтому пастухи решили оградить участок длиной h клеток.

Требуется написать программу, определяющую участок с наибольшим количеством коров. Если таких участков несколько, то нужно выбрать среди них участок с наибольшим количеством быков. Если и таких участков несколько, то нужно выбрать участок наиболее удалённый от краёв поля. Если же и таких участков несколько, то необходимо выбрать самый левый из них.

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

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

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

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

Ограничения

1 ≤ N < 10⁵, 1 ≤ h ≤ N

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

15 5
XX...XXYYYXX.YY

6 10