BoxWorld
SRM 836 · 2022-08-29 · by misof
Problem Statement
We have a table. The horizontal surface of the table is a rectangle divided into R times C unit squares.
We also have N identical white unit cubes.
We want to place all unit cubes onto the table. Each unit cube must be placed either exactly onto one of the unit squares on the table, or exactly onto the top face of another, previously placed cube.
Once we have the final arrangement built, we will paint all visible faces of all the cubes red.
We want to maximize the number of red faces. Count all arrangements of cubes that maximize this number, and return that count modulo (10^9 + 7).
Notes
- The order in which we build the arrangement of cubes does not matter. We are only counting the final configurations of all N identical cubes.
Constraints
- R will be between 1 and 14, inclusive.
- C will be between 1 and 14, inclusive.
- N will be between 1 and 100,000, inclusive.
7 10 1 Returns: 70
A 7x10 table and a single cube. We have 7x10 distinct options where to place it. Each of them is optimal: the cube will have one face touching the table and five visible faces.
1 1 47 Returns: 1
The only valid arrangement of cubes (and therefore the optimal one) is a stack of 47 cubes placed onto the only square on the table. There are 46*4 + 5 visible cube faces.
1 3 2 Returns: 1
The table is 1x3 and we have two cubes. There is a unique optimal solution: the two cubes should stand on the opposite ends of the table. This is the only configuration for which there are 10 visible cube faces.
4 6 3 Returns: 1276
1 1 1 Returns: 1
Submissions are judged against all 163 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BoxWorld with a public method int count(int R, int C, int N) · 163 test cases · 2 s / 256 MB per case