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).
Definition
- Class:
- BoxWorld
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int R, int C, int N)
- (be sure your method is public)
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.
Examples
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
1
1
2
Returns: 1
1
1
3
Returns: 1
1
1
4
Returns: 1
1
2
1
Returns: 2
1
2
2
Returns: 2
1
2
3
Returns: 2
1
2
4
Returns: 2
1
3
1
Returns: 3
1
3
2
Returns: 1
1
3
3
Returns: 2
1
3
4
Returns: 3
1
4
1
Returns: 4
1
4
2
Returns: 3
1
4
3
Returns: 6
1
4
4
Returns: 9
2
1
1
Returns: 2
2
1
2
Returns: 2
2
1
3
Returns: 2
2
1
4
Returns: 2
2
2
1
Returns: 4
2
2
2
Returns: 2
2
2
3
Returns: 4
2
2
4
Returns: 6
2
3
1
Returns: 6
2
3
2
Returns: 8
2
3
3
Returns: 2
2
3
4
Returns: 6
2
4
1
Returns: 8
2
4
2
Returns: 18
2
4
3
Returns: 12
2
4
4
Returns: 2
3
1
1
Returns: 3
3
1
2
Returns: 1
3
1
3
Returns: 2
3
1
4
Returns: 3
3
2
1
Returns: 6
3
2
2
Returns: 8
3
2
3
Returns: 2
3
2
4
Returns: 6
3
3
1
Returns: 9
3
3
2
Returns: 24
3
3
3
Returns: 22
3
3
4
Returns: 6
3
4
1
Returns: 12
3
4
2
Returns: 49
3
4
3
Returns: 84
3
4
4
Returns: 61
4
1
1
Returns: 4
4
1
2
Returns: 3
4
1
3
Returns: 6
4
1
4
Returns: 9
4
2
1
Returns: 8
4
2
2
Returns: 18
4
2
3
Returns: 12
4
2
4
Returns: 2
4
3
1
Returns: 12
4
3
2
Returns: 49
4
3
3
Returns: 84
4
3
4
Returns: 61
4
4
1
Returns: 16
4
4
2
Returns: 96
4
4
3
Returns: 276
4
4
4
Returns: 405
1
7
72567
Returns: 1702472
9
1
67168
Returns: 703171215
8
1
4
Returns: 5
1
12
1
Returns: 12
6
1
2
Returns: 10
11
1
2
Returns: 45
10
1
31726
Returns: 266338043
2
1
78772
Returns: 2
1
7
1
Returns: 7
4
1
2
Returns: 3
11
1
12727
Returns: 759796051
1
12
28647
Returns: 161322067
1
9
79254
Returns: 867604272
7
1
3
Returns: 10
1
7
40922
Returns: 724361247
11
1
95711
Returns: 547150423
1
10
2
Returns: 36
8
1
79105
Returns: 984068202
1
10
1992
Returns: 656686558
1
4
2
Returns: 3
10
11
15329
Returns: 910524176
7
2
63688
Returns: 987916155
12
7
37
Returns: 3129412
5
5
175
Returns: 608212426
4
9
5
Returns: 130318
3
4
913
Returns: 472881344
3
6
2
Returns: 126
8
3
3
Returns: 1292
2
4
4
Returns: 2
5
9
1044
Returns: 174980132
3
4
5
Returns: 18
7
12
40
Returns: 1942
5
2
4
Returns: 16
3
6
9
Returns: 2
6
5
9
Returns: 67664
11
6
32
Returns: 70
7
10
8
Returns: 933167722
8
8
52613
Returns: 531253926
11
9
5
Returns: 48690312
10
3
3906
Returns: 821228816
2
8
5
Returns: 360
9
10
16
Returns: 369058778
7
7
15
Returns: 75497964
2
11
11
Returns: 2
9
9
2145
Returns: 864872174
10
5
3
Returns: 15734
10
9
4
Returns: 1987387
10
11
882
Returns: 788380820
11
6
11548
Returns: 688793902
12
3
17
Returns: 58
14
14
98
Returns: 2
14
14
97
Returns: 200
14
14
96
Returns: 9968
14
14
93
Returns: 162730840
13
11
976
Returns: 216317011
13
13
138
Returns: 618244581
14
11
1
Returns: 154
13
14
41
Returns: 987094611
14
12
67
Returns: 820726412
13
14
5
Returns: 276225571
13
13
712
Returns: 393130702
12
11
43
Returns: 145038569
11
13
770
Returns: 489532876
11
12
31
Returns: 151970932
11
14
3220
Returns: 333272275
12
13
553
Returns: 365598932
14
13
46
Returns: 24040737
11
12
385
Returns: 242578468
12
14
22
Returns: 837588306
11
11
999
Returns: 328901243
14
13
78
Returns: 136512080
13
14
17112
Returns: 173479670
12
12
175
Returns: 713853809
12
14
17
Returns: 227161013
11
12
913
Returns: 372032695
11
13
2
Returns: 9891
14
11
3
Returns: 554666
11
12
66
Returns: 2
14
12
976
Returns: 493804066
11
11
54
Returns: 727867212
12
13
31
Returns: 534760555
11
14
3
Returns: 554666
11
13
71
Returns: 73
13
12
71
Returns: 211359362
13
11
70
Returns: 2657
11
14
102
Returns: 177118828
14
12
66
Returns: 659319717
11
14
16969
Returns: 333430403
14
11
16223
Returns: 337317217
11
12
13616
Returns: 156076388
12
14
76
Returns: 418794787
11
14
33
Returns: 791413610
12
13
34
Returns: 463861427
14
14
93
Returns: 162730840
14
14
66
Returns: 193300873