TheBrickTowerHardDivOne
SRM 554 · 2012-06-05 · by Vasyl[alphacom]
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
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.
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
Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheBrickTowerHardDivOne with a public method int find(int C, int K, long long H) · 75 test cases · 2 s / 256 MB per case