AdditionGame
SRM 498 · 2010-11-01 · by ir5
Problem Statement
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.
Constraints
- A, B and C will each be between 1 and 50, inclusive.
- N will be between 1 and 150, inclusive.
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
1 1 1 1 Returns: 1
smallest case
50 50 50 150 Returns: 3825
largest case
1 1 1 150 Returns: 3
smallest A+B+C, largest N
50 50 50 1 Returns: 50
largest A+B+C, smallest N
36 1 24 8 Returns: 260
random
36 1 24 11 Returns: 341
random
1 1 1 2 Returns: 2
Small Cases
8 20 50 76 Returns: 1519
A,B,C are all different and A+B+C > N
5 5 12 10 Returns: 78
A=B < C or A=B > C , A+B+C > N
26 26 26 39 Returns: 780
A=B=C
3 4 5 12 Returns: 31
almost A+B+C < = N
Submissions are judged against all 102 archived test cases, of which 16 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AdditionGame with a public method int getMaximumPoints(int A, int B, int C, int N) · 102 test cases · 2 s / 256 MB per case