CutAwaySquares
SRM 839 · 2022-09-30 · by misof
Problem Statement
On the table you have a piece of paper. The paper has the shape of a rectangle with the integer dimensions A times B.
You also have a paper cutter. You want to cut your paper into one or more squares. You are going to do that by repeating the following steps:
- If there are some paper squares on the table, remove them from the table.
- If there is no paper left on the table, you are done and the process terminates.
- Make a single straight cut across the paper rectangle on the table in such a way that at least one of the two new pieces is a square.
It can be shown that:
- Whenever we reach step 3, there will always be exactly one paper rectangle on the table.
- In step 3 there will always be a unique way to make the cut. (More precisely, the sizes of the two pieces after we make the cut can always be uniquely determined.)
- For any dimensions of the starting paper rectangle the process will terminate after a finite number of cuts.
Given A and B, count and return the total number of cuts we will make while dividing the A times B rectangle into squares.
Notes
- The correct answer will always fit into a signed 64-bit integer variable.
Constraints
- A will be between 1 and 10^18, inclusive.
- B will be between 1 and 10^18, inclusive.
47 47 Returns: 0
This paper is already a square. We remove it from the table and we are done. There were no cuts.
5 10 Returns: 1
We proceed as follows: Step 1: The only paper is a rectangle, we do nothing. Step 2: There is still a paper on the table, we do nothing. Step 3: We cut the 5x10 paper in half. (The cut is through the middle, parallel to the shorter sides.) This divides the paper into two 5x5 squares. Step 1: There are two squares on the table, we remove both of them. Step 2: The table is now empty, so the process ends here.
20 2 Returns: 9
In the first round we cut the paper into a 2x2 square and a 18x2 rectangle. Several similar rounds follow. In the last (9th) round in which we still make a cut we cut a 4x2 rectangle into two 2x2 squares.
42 22 Returns: 11
After two iterations of making a cut and then removing a square we get the situation from the previous example. Thus, this rectangle needs 2+9 = 11 cuts. When we are done, we'll have a 22x22 square, a 20x20 square, and ten 2x2 squares.
65455570134626 486227202717734097 Returns: 7565
20000000000000 2000000000000 Returns: 9
Watch out for integer overflow, A and B can be large. (This example is just a scaled version of Example 2, so it also requires 9 cuts.)
Submissions are judged against all 164 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CutAwaySquares with a public method long long countCuts(long long A, long long B) · 164 test cases · 2 s / 256 MB per case