FoldingPaper2
SRM 655 · 2015-03-26 · by dreamoon
Problem Statement
You have a rectangular piece of paper. Its dimensions are W times H. You want to have a paper with area A instead. Therefore, you decided to fold the paper you have. In each step you can fold the paper according to a straight line. There are two restrictions: First, that line must always be parallel to one of the rectangle's sides. Second, after each fold both dimensions of the new rectangle must be integers again.
For example, suppose that your paper is 5 units wide and 3 units tall. If you fold it according to a vertical line that is 4 units to the right of its left side, you will obtain a rectangle that is 4 units wide and 3 units tall. If you fold it according to a horizontal line that is 1 unit below the top of the rectangle, you will get a rectangle that is 5 units wide and 2 units tall.
You are given the
Constraints
- H, W will be between 1 and 1,000,000,000, inclusive.
- A will be between 1 and 100,000, inclusive.
5 3 12 Returns: 1
The solution in this case is the first example mentioned above.
2 2 3 Returns: -1
A 2x2 square cannot be folded into a rectangle with area 3. Note that a rectangle that is 1.5 units wide and 2 units tall is not a solution: both dimensions of all rectangles you produce must be integers.
4 4 1 Returns: 4
127 129 72 Returns: 8
1 100000 100000 Returns: 0
The paper already has the desired area, so no folding is necessary.
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoldingPaper2 with a public method int solve(int W, int H, int A) · 77 test cases · 2 s / 256 MB per case