Vasya cut out a rectangle of size $$$m \times n$$$ cells from paper. Petya, at each step, cuts out the largest possible square from the rectangle and keeps it. Write a program to determine how many squares will Petya eventually have?
Consider the example. Suppose the initial rectangle has a size of 3 x 5. In the first step, Petya will cut out a 3 x 3 square, leaving a rectangle of 3 x 2. In the second step, Petya will cut out a 2 x 2 square, leaving a rectangle of 1 x 2. In the third step, Petya will cut out a 1 x 1 square, and in the fourth step, he will take the remaining 1 x 1 square. In total, he will have 4 squares.
Two integers $$$m$$$ and $$$n$$$ are given, each on a separate line ($$$1 \le m, n \le 2 \cdot 10^9$$$).
Output a single integer — the number of squares.
35
4
Solutions that work correctly for $$$m, n \le 1000$$$ can earn 50 points.
Write a program to find the number of N-letter «words» composed of the letters A, B, C (by «word» we mean any sequence of consecutive letters) such that there are no more than three letters B in them.
The integer $$$N$$$ ($$$1 \le N \le 20$$$).
Output a single integer — the number of «words» that satisfy the condition.
4
80
A certain natural number is hidden. Three statements have been made about it:
You need to determine what is the smallest natural number that could have been hidden (or if such a number does not exist). You need to find the answer for several test cases.
The first line of the input contains an integer $$$T$$$ — the number of test cases ($$$1 \le T \le 1000$$$).
In each of the following $$$T$$$ lines, five integers $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$, $$$E$$$ are given, separated by spaces ($$$0 \le A, B, C, D, E \le 10^9$$$).
For each test case, output the smallest natural number that could have been hidden. If such numbers do not exist, output -1.
Solutions that work for $$$T=1$$$ and $$$A, B, C, D, E \le 100$$$ will be scored 40 points.
25 8 4 10 37 8 7 3 9
5 -1
Note for participants writing in Python. You can read 5 numbers entered with spaces like this:
a, b, c, d, e = map(int, input().split())
Andrey fills a table in a «snake» pattern: in the first row, he writes numbers in increasing order from left to right, starting with 1, then he continues in the second row from right to left, then in the third row — again from left to right, and so on. In this table, a 2 x 2 fragment was found with the numbers
| a+1 | a |
| b | b+1 |
Determine the maximum number of columns that could have been in Andrey's table.
Two integers $$$a$$$ and $$$b$$$ are given, each on a separate line ($$$1 \le a, b \le 10^9$$$).
Output a single integer — the answer. If there is no solution, output -1.
Solutions that work correctly for $$$a, b \le 1000$$$ will score at least 30 points.
Solutions that work correctly for $$$a, b \le 10^6$$$ will score at least 60 points.
48
3
The table in the example looks like this:
| 1 | 2 | 3 |
| 6 | 5 | 4 |
| 7 | 8 | 9 |
An unordered pair of natural numbers is called good if one of the numbers divides the other. Output $$$n$$$ such natural numbers not exceeding one million, such that there are exactly $$$k$$$ good pairs among them, or determine that this is impossible.
More formally: for the numbers output by your program $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, there must be exactly $$$k$$$ pairs of indices $$$i$$$, $$$j$$$, where $$$i \lt j$$$, such that $$$a_i$$$ divides $$$a_j$$$ or $$$a_j$$$ divides $$$a_i$$$.
Two integers $$$n$$$ and $$$k$$$ are given, each on a separate line ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^5$$$).
Output $$$n$$$ such natural numbers in the range from 1 to $$$10^{6}$$$, such that there are exactly $$$k$$$ good pairs among them. If there are multiple correct answers, output any. If there are no solutions, output -1.
Subtask 1 (up to 30 points): $$$n \le 5$$$.
Subtask 2 (up to 30 points): $$$n \le 100$$$.
Subtask 3 (up to 40 points): no additional constraints.
43
2 2 4 7
2100
-1