TopCoder problem "AdditionGame" used in SRM 498 (Division II Level One)



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

0)
    
3
4
5
3
Returns: 13

The three numbers written on the blackboard are (3, 4, 5). One possible optimal strategy is as follows:

  1. Ciel chooses 5. She gains 5 points, and the numbers become (3, 4, 4).
  2. Ciel chooses 4. She gains 4 points, and the numbers become (3, 3, 4).
  3. 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
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.

2)
    
3
5
48
40
Returns: 1140

The only optimal strategy is to choose the following numbers: 48, 47, 46, ..., 11, 10, 9.

3)
    
36
36
36
13
Returns: 446
4)
    
8
2
6
13
Returns: 57

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11317

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14427&pm=11317

Writer:

ir5

Testers:

PabloGilberto , ivan_metelsky , sl2 , pieguy

Problem categories:

Greedy, Simple Math, Simple Search, Iteration