FoxPaintingBalls | Topcoder Archive

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 longs R, G, and B. You are also given the int N. Return the maximum possible number of Ball Triangles Jiro can paint.

Definition

Class:: FoxPaintingBalls
Method:: theMax
Parameters:: long, long, long, int
Returns:: long
Method signature:: long theMax(long R, long G, long B, int N)
(be sure your method is public)

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.

Examples

```
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
```

19330428391852493

48815737582834113

11451481019198930

Returns: 5750952686

```
1
```
```
1
```
```
1
```
```
1
```
```
Returns: 3
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.