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:
- TheBrickTowerHardDivOne
- Method:
- find
- Parameters:
- int, int, long
- Returns:
- int
- Method signature:
- int find(int C, int K, long H)
- (be sure your method is public)
Constraints
- C will be between 1 and 4747, inclusive.
- K will be between 0 and 7, inclusive.
- H will be between 1 and 474,747,474,747,474,747, 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
1915
2
270237332186251130
Returns: 577774846
436
0
168885346568379548
Returns: 153124335
446
2
207964594444828076
Returns: 1030353246
4
7
288230376151711743
Returns: 299956365
5
7
288230376151711742
Returns: 994419489
6
7
288230376151711743
Returns: 986187124
5
7
288230376151711743
Returns: 205582709
12
7
288230376151711742
Returns: 1224459501
2027
6
133181695103836835
Returns: 472698391
4667
4
73464431133633209
Returns: 449435632
670
4
413748111775473632
Returns: 447024516
2608
1
205759520386358386
Returns: 314836316
3995
4
105613179963725261
Returns: 305888919
3
2
472257534206452389
Returns: 149730924
2
0
451713629396661978
Returns: 850637221
3
2
460489846970080531
Returns: 129067595
3
5
452355762451943573
Returns: 472496835
2
3
445593500669332620
Returns: 761672093
4747
7
474747474747474747
Returns: 473182063
4747
0
474747474747474747
Returns: 1074025271
2
7
474747474747474747
Returns: 157811468
3
7
474747474747474747
Returns: 556349242
7
7
288230376151711743
Returns: 956141240
6
7
288230376151711743
Returns: 986187124
5
7
288230376151711742
Returns: 994419489
6
7
288230376151711742
Returns: 132703428
4747
7
288230376151711742
Returns: 117928610
4747
7
12345678901357924
Returns: 886585892