FoldingPaper2 | Topcoder Archive

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 ints W, H, and A. If it is impossible to fold the paper into a valid rectangle with area A, return -1. Otherwise, return the smallest number of times you need to fold the paper.

Definition

Class:: FoldingPaper2
Method:: solve
Parameters:: int, int, int
Returns:: int
Method signature:: int solve(int W, int H, int A)
(be sure your method is public)

Constraints

H, W will be between 1 and 1,000,000,000, inclusive.
A will be between 1 and 100,000, inclusive.

Examples

```
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.
```
1
```
```
1
```
```
2
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.