Вася вырезал из бумаги прямоугольник размером $$$m \times n$$$ клеток. Петя на каждом шаге отрезает от прямоугольника квадрат наибольшего размера и забирает себе. Напишите программу, определяющую, сколько квадратов в итоге окажется у Пети.
Рассмотрим пример. Пусть изначально прямоугольник имеет размер 3 x 5. На первом шаге Петя вырежет квадрат 3 x 3, и останется прямоугольник 3 x 2. На втором шаге Петя вырежет квадрат 2 x 2, и останется прямоугольник 1 x 2. На третьем шаге Петя вырежет квадрат 1 x 1, и на четвёртом шаге заберёт оставшийся квадрат 1 x 1. Итого у него будет 4 квадрата.
Вводятся два целых числа $$$m$$$ и $$$n$$$, каждое в отдельной строке ($$$1 \le m, n \le 2 \cdot 10^9$$$).
Выведите одно целое число — количество квадратов.
35
4
Решения, правильно работающие при $$$m, n \le 1000$$$, могут набрать 50 баллов.
Напишите программу для нахождения количества N-буквенных "слов", составленных из букв А, Б, В (под "словом" понимается любая последовательность подряд идущих букв) таких, что в них есть не более трёх букв Б.
Вводится одно целое число $$$N$$$ ($$$1 \le N \le 20$$$).
Выведите одно целое число — количество "слов", удовлетворяющих условию.
4
80
Загадано некоторое натуральное число. О нём сделаны три утверждения:
Требуется определить, какое наименьшее натуральное число могло быть загадано (или что такого числа не существует). Вам нужно найти ответ для нескольких наборов входных данных.
В первой строке входных данных вводится целое число $$$T$$$ — количество наборов входных данных ($$$1 \le T \le 1000$$$).
В каждой из следующих $$$T$$$ строк вводятся через пробел пять целых чисел $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$, $$$E$$$ ($$$0 \le A, B, C, D, E \le 10^9$$$).
Для каждого набора входных данных выведите наименьшее натуральное число, которое могло быть загадано. Если таких чисел нет, то выведите -1.
Решения, работающие при $$$T=1$$$ и $$$A, B, C, D, E \le 100$$$, будут оцениваться из 40 баллов.
25 8 4 10 37 8 7 3 9
5 -1
Примечание для участников, пишущих на Python. Прочитать 5 чисел, введённых через пробел, можно так:
a, b, c, d, e = map(int, input().split())
Андрей заполняет таблицу «змейкой»: в первой строке слева направо выписывает по возрастанию числа, начиная с 1, потом продолжает во второй строке справа налево, потом в третьей строке — снова слева направо, и так далее. В этой таблице нашёлся фрагмент 2 x 2 с числами
| a+1 | a |
| b | b+1 |
Определите, какое наибольшее количество столбцов могло быть в таблице Андрея.
Вводятся два целых числа $$$a$$$ и $$$b$$$, каждое в отдельной строке ($$$1 \le a, b \le 10^9$$$).
Выведите одно целое число — ответ. Если решения нет, выведите -1.
Решения, верно работающие при $$$a, b \le 1000$$$, смогут набрать не менее 30 баллов.
Решения, верно работающие при $$$a, b \le 10^6$$$, смогут набрать не менее 60 баллов.
48
3
Таблица в примере выглядит так:
| 1 | 2 | 3 |
| 6 | 5 | 4 |
| 7 | 8 | 9 |
Неупорядоченная пара натуральных чисел называется хорошей, если в этой паре одно из чисел делится на другое. Выведите $$$n$$$ таких натуральных чисел, не превышающих миллиона, чтобы среди них было ровно $$$k$$$ хороших пар, либо определите, что это невозможно.
Более формально: для выведенных вашей программой чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ должно найтись ровно $$$k$$$ таких пар индексов $$$i$$$, $$$j$$$, где $$$i \lt j$$$, что $$$a_i$$$ делится на $$$a_j$$$ или $$$a_j$$$ делится на $$$a_i$$$.
Вводится два целых числа $$$n$$$ и $$$k$$$, каждое в отдельной строке ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^5$$$).
Выведите $$$n$$$ таких натуральных чисел из диапазона от 1 до $$$10^{6}$$$, чтобы среди них было ровно $$$k$$$ хороших пар. Если есть несколько правильных ответов, выведите любой. Если решений нет, выведите -1.
Подзадача 1 (до 30 баллов): $$$n \le 5$$$.
Подзадача 2 (до 30 баллов): $$$n \le 100$$$.
Подзадача 3 (до 40 баллов): нет дополнительных ограничений.
43
2 2 4 7
2100
-1