FoxPaintingBalls
SRM 552 · 2012-06-05 · by wrong
Problem Statement
A Ball Triangle is a set of identical balls placed in a triangular shape. A Ball Triangle has N rows, numbered 1 to N from top to bottom. For all i, 1 <= i <= N, the i-th row contains i balls. For example, the following image shows a Ball Triangle with N=3.
Fox Jiro has infinitely many Ball Triangles. He can paint a Ball Triangle according to the following conditions:
- Each of the balls has to be painted either red, green, or blue.
- No two adjacent balls may share the same color.
The following image shows one valid coloring of a Ball Triangle for N=3.
Jiro wants to paint as many Ball Triangles as he can. As long as he follows the rules above, he may color the Ball Triangles in any way he likes. Some of the colored Ball Triangles may look exactly the same, but they don't have to. The only other constraint is the total amount of paint available to Jiro: In all the triangles together, he can paint at most R balls red, G balls green, and B balls blue.
You are given the
Constraints
- R, G and B will each be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- N will be between 1 and 1,000,000,000, inclusive.
2 2 2 3 Returns: 1
Jiro can paint one Ball Triangle in the same way as in the image in the statement.
1 2 3 3 Returns: 0
This time Jiro can paint no Ball Triangles.
8 6 6 4 Returns: 2
7 6 7 4 Returns: 2
100 100 100 4 Returns: 30
Submissions are judged against all 229 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoxPaintingBalls with a public method long long theMax(long long R, long long G, long long B, int N) · 229 test cases · 2 s / 256 MB per case