Problem Statement

You have a rectangular cake of a given length and width, and want to divide it into a certain number of equal-area rectangular pieces. Each cut you make must be parallel to the sides of the cake, and must completely cut one of the existing pieces into two parts. (Therefore, cutting the cake into N pieces will require exactly N-1 cuts.)

You prefer square pieces to those with a larger aspect ratio. (Here, we define the "aspect ratio" of a piece to be the length of its longer side divided by the length of its shorter side.) You should cut the cake in such a way as to minimize the maximum aspect ratio of all the resulting pieces.

For example, if the cake is 2x3, and you want to cut it into six pieces, you can cut it into six 1x1 pieces. Each piece has an aspect ratio of 1.0, which is the smallest possible aspect ratio. Therefore, this solution is optimal.

One way to cut a 5x5 cake into 5 pieces is to first cut it into two pieces of sizes 2x5 and 3x5. Cut the smaller of these two in half (each of size 2 x 5/2) and the larger in thirds (each of size 3 x 5/3). The largest aspect ratio of these five pieces is 3/(5/3) = 1.8. There is no way to cut this cake into 5 equal-area pieces that all have an aspect ratio of less than 1.8

Definition

 Class: CakeDivision Method: ratio Parameters: int, int, int Returns: double Method signature: double ratio(int length, int width, int pieces) (be sure your method is public)

Notes

-Your return value must have an absolute or relative error less than 1e-9.

Constraints

-length and width will be between 1 and 1000, inclusive.
-pieces will be between 1 and 10, inclusive.

Examples

0)

 2 3 6
Returns: 1.0
 This is the first example in the problem statement.
1)

 5 5 5
Returns: 1.8
 This is the second example in the problem statement.
2)

 333 333 9
Returns: 1.0
 The cake can be cut into 9 squares.
3)

 500 1 10
Returns: 50.0
 The optimal solution is to cut the cake into 10 50x1 pieces.
4)

 950 430 9
Returns: 1.2573099415204678

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3944

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6536&pm=3944

legakis

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Simple Math