Problem Statement
You can cut the block of cheese into smaller pieces. You are only allowed to cut as follows:
- Each cut must divide one block of cheese into two smaller blocks of cheese.
- Each cut must be parallel to one of the faces of the piece you are cutting.
- Each of the two smaller blocks must have integer dimensions.
When placing a block of cheese onto a piece of bread, the cheese is always rotated so that its shortest side is vertical. In other words, suppose you have a block of cheese with dimensions (X,Y,Z) such that X ≥ Y ≥ Z. If you place this block onto a piece of bread, its surface area will be X*Y and its thickness will be Z.
A block of cheese is called a good slice if and only if its thickness is greater than or equal to S. (Recall that the thickness of a block is the length of its shortest side.)
You can cut your block of cheese into arbitrarily many pieces, as long as you follow the rules given above. Your goal is to cut the block in such a way that maximizes the total surface area of all good slices among the pieces. Note that your way of cutting may also produce some pieces that are not good slices, but those pieces won't contribute to the surface area. The number of good slices does not matter, we only care about their surface. Different good slices may have different dimensions.
You are given the
Definition
- Class:
- CheeseSlicing
- Method:
- totalArea
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int totalArea(int A, int B, int C, int S)
- (be sure your method is public)
Constraints
- A, B and C will be between 1 and 100, inclusive.
- S will be between 1 and 10, inclusive.
Examples
1
3
3
2
Returns: 0
One of the dimensions of this block is 1. Regardless of how we cut it, each piece will have one dimension equal to 1. As S=2, this means that producing a good slice is impossible. Hence, the maximum total surface area of good slices is 0.
5
3
5
3
Returns: 25
The entire block is a good slice with thickness 3 and surface area 5*5 = 25. An optimal solution is to make no cuts and to simply take this one block.
5
5
5
2
Returns: 58
One possible sequence of cuts: 5x5x5 -> 2x5x5 + 3x5x5 3x5x5 -> 3x2x5 + 3x3x5 3x3x5 -> 3x3x2 + 3x3x3 After these three cuts we have four pieces: 2x5x5, 3x2x5, 3x3x2, and 3x3x3. Each of these is a good slice. Their total surface area is 5*5 + 3*5 + 3*3 + 3*3.
49
92
20
3
Returns: 30045
1
1
1
1
Returns: 1
Min test: 1x1x1 piece is a slice of area 1
100
100
100
1
Returns: 1000000
Max test: sliced in 100 of 1x100x100 pieces
5
5
5
4
Returns: 25
No cuts can be done to improve
13
14
15
7
Returns: 390
One cut to make two slices
7
8
9
10
Returns: 0
S > thickness of the slice
37
54
93
9
Returns: 20646
50
7
79
4
Returns: 6888
99
68
84
8
Returns: 70632
54
94
55
1
Returns: 279180
95
57
3
10
Returns: 0
67
72
85
5
Returns: 82008
51
61
13
8
Returns: 4992
1
20
36
9
Returns: 0
25
81
69
4
Returns: 34925
39
48
87
7
Returns: 23205
67
22
4
2
Returns: 2948
68
10
32
2
Returns: 10880
66
86
53
5
Returns: 60156
57
37
49
9
Returns: 11465
49
61
76
9
Returns: 25148
32
64
89
7
Returns: 26020
44
57
82
4
Returns: 51414
56
21
70
2
Returns: 41160
42
25
93
1
Returns: 97650
34
24
74
1
Returns: 60384
62
78
35
8
Returns: 21084
14
36
29
4
Returns: 3654
48
4
62
10
Returns: 0
19
2
88
2
Returns: 1672
59
21
95
4
Returns: 29414
41
16
36
5
Returns: 4716
40
80
95
5
Returns: 60800
56
21
28
7
Returns: 4704
98
62
86
4
Returns: 130616
49
14
77
7
Returns: 7546
18
91
76
8
Returns: 15528
92
15
50
2
Returns: 34500
35
96
16
6
Returns: 8960
64
3
62
3
Returns: 3968
82
8
80
7
Returns: 7480
28
7
5
6
Returns: 0
20
91
41
9
Returns: 8274
4
69
65
3
Returns: 5980
59
92
61
3
Returns: 110361
6
62
4
2
Returns: 744
9
71
19
2
Returns: 6066
73
80
27
7
Returns: 22470
88
6
95
7
Returns: 0
12
100
92
1
Returns: 110400
42
84
99
7
Returns: 49896
53
15
70
3
Returns: 18550
6
82
65
3
Returns: 10660
43
21
55
3
Returns: 16555
91
25
75
6
Returns: 28427
5
1
74
4
Returns: 0
31
97
91
4
Returns: 68397
8
7
9
8
Returns: 0
100
100
100
10
Returns: 100000
3
3
4
2
Returns: 18
100
100
1
2
Returns: 0
9
9
9
3
Returns: 243
8
4
4
3
Returns: 36
70
84
23
2
Returns: 67620
3
3
3
4
Returns: 0
8
50
74
9
Returns: 0
5
3
7
2
Returns: 48
6
6
6
3
Returns: 72
10
10
10
3
Returns: 328
2
2
1
2
Returns: 0
7
9
20
6
Returns: 198
4
4
3
2
Returns: 24