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.
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
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
36
1
24
12
Returns: 366
36
1
24
13
Returns: 390
36
1
24
14
Returns: 414
1
1
1
2
Returns: 2
Small Cases
1
1
1
3
Returns: 3
1
1
1
4
Returns: 3
2
1
2
1
Returns: 2
2
2
1
2
Returns: 4
1
2
2
3
Returns: 5
1
2
2
4
Returns: 6
1
2
2
5
Returns: 7
8
20
50
76
Returns: 1519
A,B,C are all different and A+B+C > N
8
50
20
33
Returns: 1124
20
8
50
29
Returns: 1044
20
50
8
47
Returns: 1341
50
8
20
8
Returns: 372
50
20
8
17
Returns: 714
23
40
47
16
Returns: 652
23
47
40
34
Returns: 1219
40
23
47
51
Returns: 1614
40
47
23
34
Returns: 1219
47
23
40
109
Returns: 2223
47
40
23
13
Returns: 542
21
35
50
66
Returns: 1849
21
50
35
53
Returns: 1641
35
21
50
17
Returns: 715
35
50
21
49
Returns: 1566
50
21
35
5
Returns: 240
50
35
21
34
Returns: 1229
25
46
48
73
Returns: 2206
25
48
46
28
Returns: 1135
46
25
48
26
Returns: 1067
46
48
25
106
Returns: 2547
48
25
46
100
Returns: 2512
48
46
25
31
Returns: 1233
28
38
50
27
Returns: 1055
28
50
38
22
Returns: 894
38
28
50
70
Returns: 2046
38
50
28
93
Returns: 2322
50
28
38
86
Returns: 2257
50
38
28
84
Returns: 2235
5
5
12
10
Returns: 78
A=B < C or A=B > C , A+B+C > N
5
12
5
7
Returns: 63
12
5
5
16
Returns: 99
12
12
5
4
Returns: 46
12
5
12
16
Returns: 136
5
12
12
8
Returns: 84
3
3
13
4
Returns: 46
3
13
3
15
Returns: 98
13
3
3
11
Returns: 88
13
13
3
12
Returns: 126
13
3
13
16
Returns: 152
3
13
13
15
Returns: 146
3
3
27
17
Returns: 323
3
27
3
2
Returns: 53
27
3
3
4
Returns: 102
27
27
3
3
Returns: 80
27
3
27
4
Returns: 106
3
27
27
10
Returns: 250
26
26
26
39
Returns: 780
A=B=C
26
26
26
40
Returns: 793
26
26
26
41
Returns: 806
3
4
5
12
Returns: 31
almost A+B+C < = N
8
1
19
28
Returns: 227
3
13
2
18
Returns: 100
50
49
47
146
Returns: 3628
43
49
44
137
Returns: 3161
43
49
44
135
Returns: 3160
41
48
39
129
Returns: 2817
41
48
39
127
Returns: 2816
50
49
50
150
Returns: 3775
22
33
41
149
Returns: 1675
5
4
10
1
Returns: 10
1
1
1
10
Returns: 3
2
3
4
15
Returns: 19
3
2
1
6
Returns: 10
2
2
2
20
Returns: 9
2
2
2
6
Returns: 9
1
1
1
12
Returns: 3
2
3
4
3
Returns: 10
5
4
18
9
Returns: 126
1
10
15
100
Returns: 176
5
4
1
4
Returns: 16
1
1
1
6
Returns: 3
1
3
2
1
Returns: 3
3
2
1
10
Returns: 10
5
6
1
6
Returns: 27
1
1
1
50
Returns: 3
3
1
2
1
Returns: 3
5
5
40
40
Returns: 828
1
1
1
5
Returns: 3