Problem Statement
John and Brus are building towers using toy bricks. They have an unlimited supply of bricks of C different colors. Each brick is a 1x1x1 cube. A tower of height X is a 2x2xX rectangular prism, built using 4X bricks.
John and Brus want their towers to look nice. A tower is nice if it has the following two properties:
- There are at most K pairs of neighboring bricks with the same color. (Two bricks are neighboring if they share a common side.)
- The height of the tower is between 1 and H, inclusive.
You are given the
Definition
- Class:
- TheBrickTowerHardDivTwo
- Method:
- find
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int find(int C, int K, int H)
- (be sure your method is public)
Constraints
- C will be between 1 and 4, inclusive.
- K will be between 0 and 7, inclusive.
- H will be between 1 and 47, inclusive.
Examples
2
0
2
Returns: 4
No two neighboring bricks may share the same color. As we only have two colors, the entire tower must be colored like a chessboard. There are two such towers of height 1, and two of height 2.
1
7
19
Returns: 1
Only one tower of height 1 is acceptable here.
2
3
1
Returns: 14
There are 16 possible towers of height 1. If all bricks share the same color, the tower is not nice. There are two such towers. Each of the remaining 14 towers is nice.
4
7
47
Returns: 1008981254
1
3
19
Returns: 0
3
6
26
Returns: 63744861
1
5
15
Returns: 1
4
2
42
Returns: 546398371
1
0
32
Returns: 0
4
2
19
Returns: 948231878
4
5
12
Returns: 867619386
1
3
43
Returns: 0
3
6
15
Returns: 198242641
1
5
33
Returns: 1
1
3
11
Returns: 0
2
6
24
Returns: 16094
1
4
15
Returns: 1
1
4
43
Returns: 1
3
1
10
Returns: 1220741998
2
4
39
Returns: 8426
4
6
45
Returns: 675895602
3
4
44
Returns: 1175696211
4
6
46
Returns: 133331749
4
5
44
Returns: 485822408
4
2
4
Returns: 80001192
4
0
8
Returns: 978491432
4
2
9
Returns: 752462956
4
5
1
Returns: 256
4
3
17
Returns: 577534162
4
6
6
Returns: 941725416
4
7
47
Returns: 1008981254
4
0
47
Returns: 699527058
4
0
10
Returns: 864059624
1
0
23
Returns: 0
4
0
12
Returns: 294638799
4
0
21
Returns: 160339243
1
0
19
Returns: 0
3
0
26
Returns: 1122838812
1
0
29
Returns: 0
1
0
34
Returns: 0
2
2
8
Returns: 28
1
0
23
Returns: 0
2
2
6
Returns: 24
2
5
21
Returns: 3304
1
3
7
Returns: 0
1
6
4
Returns: 1
1
5
7
Returns: 1
4
6
47
Returns: 240414241
4
5
47
Returns: 734623669
4
7
46
Returns: 1064072547