AdditionGame | Topcoder Archive

Problem Statement

Fox Ciel is playing a game called Addition Game.

Three numbers A, B and C are written on a blackboard, and Ciel initially has 0 points. She repeats the following operation exactly N times: She chooses one of the three numbers on the blackboard. Let X be the chosen number. She gains X points, and if X >= 1, the number X on the blackboard becomes X-1. Otherwise, the number does not change.

Return the maximum number of points she can gain if she plays optimally.

Definition

Class:: AdditionGame
Method:: getMaximumPoints
Parameters:: int, int, int, int
Returns:: int
Method signature:: int getMaximumPoints(int A, int B, int C, int N)
(be sure your method is public)

Constraints

A, B and C will each be between 1 and 50, inclusive.
N will be between 1 and 150, inclusive.

Examples

```
3
```
```
4
```
```
5
```
```
3
```
```
Returns: 13
```
The three numbers written on the blackboard are (3, 4, 5). One possible optimal strategy is as follows: Ciel chooses 5. She gains 5 points, and the numbers become (3, 4, 4). Ciel chooses 4. She gains 4 points, and the numbers become (3, 3, 4). Ciel chooses 4. She gains 4 points, and the numbers become (3, 3, 3). She gains a total of 5+4+4=13 points.
```
1
```
```
1
```
```
1
```
```
8
```
```
Returns: 3
```
One optimal strategy is to choose a 1 in each of the first three turns, for a total of 3 points. The numbers then become (0, 0, 0). After that, she won't be able to gain any more points.
```
3
```
```
5
```
```
48
```
```
40
```
```
Returns: 1140
```
The only optimal strategy is to choose the following numbers: 48, 47, 46, ..., 11, 10, 9.
```
36
```
```
36
```
```
36
```
```
13
```
```
Returns: 446
```
```
8
```
```
2
```
```
6
```
```
13
```
```
Returns: 57
```

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.