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
2
3
6
Returns: 1.0
This is the first example in the problem statement.
5
5
5
Returns: 1.8
This is the second example in the problem statement.
333
333
9
Returns: 1.0
The cake can be cut into 9 squares.
500
1
10
Returns: 50.0
The optimal solution is to cut the cake into 10 50x1 pieces.
950
430
9
Returns: 1.2573099415204678
1
1
10
Returns: 1.6
10
10
10
Returns: 1.6
100
100
10
Returns: 1.6
1000
1000
10
Returns: 1.6
1
1
8
Returns: 2.0
1000
1000
7
Returns: 1.75
999
1000
10
Returns: 1.5984
1000
998
10
Returns: 1.5968
1
1000
10
Returns: 100.0
1000
1
1
Returns: 1000.0
324
984
9
Returns: 1.7083333333333333
23
782
8
Returns: 4.25
526
623
7
Returns: 1.5228136882129277
4
5
10
Returns: 1.3888888888888888
998
999
3
Returns: 2.996996996996997
1000
599
9
Returns: 1.663888888888889
1000
600
9
Returns: 1.6666666666666667
1000
601
9
Returns: 1.663893510815308
10
9
10
Returns: 1.44
1000
1000
10
Returns: 1.6
10
10
1
Returns: 1.0