CheeseSlicing
TCO17 Round 1A · 2017-03-31 · by Nickolas
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
Constraints
- A, B and C will be between 1 and 100, inclusive.
- S will be between 1 and 10, inclusive.
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
Submissions are judged against all 75 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CheeseSlicing with a public method int totalArea(int A, int B, int C, int S) · 75 test cases · 2 s / 256 MB per case