Задача 1. Олимпиада ≡

Условие

Герман и Руслан участвуют в олимпиаде по программированию. На этой олимпиаде задачи оцениваются следующим образом: первая задача даёт 1 балл, вторая задача даёт 2 балла, третья задача даёт 3 балла и так до бесконечности. При этом задачу i можно решить только в том случае, если решена задача i − 1. Первая задача открыта участникам с самого начала.

Герман на этой олимпиаде решил n задач. Когда он решил узнать, сколько задач решил Руслан, Руслан сказал: "Не хочу говорить... Скажу лишь то, что у меня в k раз меньше баллов, чем у тебя." Герман, из информации, которая у него есть, все равно решил узнать, сколько же задач решил Руслан. Он просит Вас написать программу, которая сообщит ему количество задач, решенных Русланом.

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

В первой строке подается два натуральных числа n и k — количество задач, решенных Германом, и во сколько раз у Руслана меньше баллов, чем у Германа соответственно.

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

Выведите одно число - количество задач, которое решил Руслан. Гарантируется, что ответ существует.

Ограничения

1 ≤ n, k ≤ 10⁹

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

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

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

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

9 3

5

Задача 2. Очень круглое число ≡

Условие

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

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

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

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

Выведите одно натуральное число — ответ на вопрос задачи. Если таких чисел нет, выведите  − 1.

Ограничения

1 ≤ n ≤ 10¹⁵

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

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

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

В примере дано n = 1. Первый факториал, заканчивающийся на один ноль, это 5!, он равен 120.

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

1

5

Задача 3. Прямоугольники ≡

Условие

Математик Герман очень любит прямоугольники. Сегодня он взял листок бумаги и расставил n точек на нем. После этого у него осталась одна точка, которую он может поставить куда угодно. Он хочет поставить эту точку так, чтобы можно было построить прямоугольник максимальной площади с вершинами в поставленных точках и сторонами, параллельными осям координат. Какая максимально возможная площадь прямоугольника может получится у Германа?

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

В первой строке записано натуральное число n — количество точек. В следующих n строках записано по два числа y_i и x_i.

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

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

Ограничения

3 ≤ n ≤ 2500

 − 300 ≤ y_i, x_i ≤ 300

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

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

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

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

В первом примере Герман должен поставить еще одну точку в начало координат.

Во втором примере Герман может поставить оставшуюся точку в координаты (3; 3). Тогда у него получится прямоугольник площадью 9.

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

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

4
0 1
0 2
2 0
2 2

4

7
0 0
2 0
0 2
2 2
3 0
0 3
3 2

9

3
0 1
2 0
0 3

-1

Задача 4. Дробные монеты ≡

Условие

В одном государстве в обращении находятся монеты достоинством xy бурлей, где 1 ≤ x < y и xy — несократимая дробь. Например, при y = 5 в ходу монеты достоинством 15, 25, 35 и 45 бурлей, а при y = 6 — монеты 16 и 56.

Хорошим тоном для банковских работников страны является набор требуемой суммы наименьшим количеством монет. Например, если клиент хочет снять сумму 136, ему выдадут пять монет: две монеты достоинством 56 и три монеты достоинством 16.

Определите наименьшее количество монет для набора требуемой денежной суммы py.

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

Первая строка входного файла содержит натуральное число p — числитель требуемой для выдачи суммы, вторая строка содержит натуральное число y — знаменатель достоинств всех монет в стране.

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

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

Ограничения

1 ≤ p ≤ 10⁵

2 ≤ y ≤ 100

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

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

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

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

В первом примере дано y = 15. В обращении находятся монеты достоинством 115, 215, 415, 715, 815, 1115, 1315 и 1415.

Для набора суммы 1715 достаточно взять две монеты, например 1315 и 415.

Во втором примере дано y = 2. В обращении находятся только монеты достоинством 12.

Для набора суммы 42 = 21 необходимо взять четыре монеты.

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

17
15

2

4
2

4

Задача 5. Треугольник Фибоначчи ≡

Условие

Числа Фибоначчи — элементы бесконечной числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … , в которой первые два числа равны 1 и 1, а каждое последующее число равно сумме двух предыдущих чисел.

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

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

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

В единственной строке записано натуральное число n.

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

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

Ограничения

1 ≤ n ≤ 10¹⁸

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

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

Подзадача 1: 1 ≤ n ≤ 10³, баллы: 30.

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

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

Число 2 первый раз встречается в третьей строке треугольника, число 10 — в седьмой, число 12 не встречается вообще.

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

2

3

10

7

12

-1

Задача 6. Скалолаз ≡

Условие

Артем с раннего детства увлекается скалолазанием. Сегодня он решил покорить крупный горный хребет в своем городе.

Горный хребет представлен прямоугольником размером h × w метров. Каждая гора на этом хребте занимает квадрат 1 × 1 метр. Гора с координатами (x; y) имеет высоту h_y,x метров. Чтобы перебираться между горами, Артём использует канат. Для того, чтобы перебраться с горы x,y на гору i,j, длина каната должна быть большей или равной разнице высот двух гор.

Двигаться Артем может только на соседние по горизонтали или вертикали горы.

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

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

В первой строке записано два натуральных числа h и w — размеры горного хребта. В следующих h строках записано по w чисел h_{i, j} — высоты гор.

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

Программа должна вывести одно число — минимальную длину каната, при помощи которого можно перейти с левой на правую сторону.

Ограничения

2 ≤ h, w ≤ 1000

1 ≤ h_{i, j} ≤ 10⁹

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

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

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

3 3
4 9 7
6 8 1
8 1 1

2