Problem Statement
You have a deck of cards containing n red and m black cards. Initially, you have c chips. The cards are shuffled and then dealt one after another. Before each card is dealt, you place a bet of B chips (where B is between 0 and the number of chips you have left, inclusive) and predict whether that card will be red or black. If your prediction is correct, you receive back the B chips that you bet and win an additional B chips. If your prediction is incorrect, you lose the B chips that you bet.
You are a cautious player, so your strategy is to play in such a way that maximizes the number of chips you have at the end of the game in the worst possible case. In other words, your strategy must guarantee that you end the game with at least X chips, regardless of the order of cards in the deck, where X is as large as possible. Return this value of X.
For example, let n = 1, m = 2 and c = 3. The following optimal strategy will guarantee that you end the game with at least 8 chips: Bet 1 chip that the first card is black. If it is, you will then have 4 chips. Skip the next card, and bet all 4 chips on the last card. You will know the color of that last card because you will have already seen the other two cards. If you lose your first bet, you will have 2 chips left, and the two remaining cards will be black. Bet all your chips on each of the remaining cards, and you will double your chips twice, for a total of 8 chips. No other strategy can guarantee more than 8 chips in the worst case.
Definition
- Class:
- PredictionCardGame
- Method:
- winnings
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int winnings(int n, int m, int c)
- (be sure your method is public)
Constraints
- n and m will each be between 0 and 10, inclusive.
- c will be between 1 and 30, inclusive.
Examples
1
2
3
Returns: 8
The example from the problem statement.
10
0
30
Returns: 30720
This time all cards are red, so you must bet each time.
1
1
1
Returns: 2
Do not bet on the first card (or you can lose everything).
10
10
1
Returns: 2
You cannot split your chip, so you must wait until all the remaining cards are of the same color. In the worst case, this will not happen until there is only one card left.
2
3
7
Returns: 20
0
0
30
Returns: 30
0
1
30
Returns: 60
2
0
30
Returns: 120
0
3
30
Returns: 240
0
4
30
Returns: 480
5
0
30
Returns: 960
0
6
30
Returns: 1920
0
7
30
Returns: 3840
0
8
30
Returns: 7680
0
9
30
Returns: 15360
0
10
30
Returns: 30720
1
1
30
Returns: 60
1
2
30
Returns: 80
3
1
30
Returns: 120
1
4
30
Returns: 192
1
5
30
Returns: 320
6
1
30
Returns: 544
1
7
30
Returns: 944
8
1
30
Returns: 1666
1
9
30
Returns: 3072
10
1
30
Returns: 5504
2
2
30
Returns: 80
3
2
30
Returns: 96
2
4
30
Returns: 128
2
5
30
Returns: 176
2
6
30
Returns: 260
2
7
30
Returns: 416
2
8
30
Returns: 644
9
2
30
Returns: 1072
2
10
30
Returns: 1792
3
3
30
Returns: 96
3
4
30
Returns: 106
5
3
30
Returns: 132
3
6
30
Returns: 176
7
3
30
Returns: 256
8
3
30
Returns: 354
3
9
30
Returns: 520
10
3
30
Returns: 816
4
4
30
Returns: 106
4
5
30
Returns: 116
4
6
30
Returns: 136
4
7
30
Returns: 176
8
4
30
Returns: 232
4
9
30
Returns: 322
10
4
30
Returns: 458
5
5
30
Returns: 116
6
5
30
Returns: 128
7
5
30
Returns: 146
8
5
30
Returns: 176
9
5
30
Returns: 226
10
5
30
Returns: 298
6
6
30
Returns: 128
7
6
30
Returns: 132
8
6
30
Returns: 152
9
6
30
Returns: 176
10
6
30
Returns: 226
7
7
30
Returns: 132
7
8
30
Returns: 136
9
7
30
Returns: 160
7
10
30
Returns: 184
8
8
30
Returns: 136
9
8
30
Returns: 146
8
10
30
Returns: 162
9
9
30
Returns: 146
10
9
30
Returns: 152
10
10
30
Returns: 152
10
10
1
Returns: 2
10
10
2
Returns: 4
10
10
3
Returns: 8
10
10
4
Returns: 10
10
10
5
Returns: 16
10
10
6
Returns: 18
10
10
7
Returns: 24
10
10
8
Returns: 26
10
10
9
Returns: 32
10
10
10
Returns: 34
10
10
11
Returns: 40
10
10
12
Returns: 48
10
10
13
Returns: 52
10
10
14
Returns: 56
10
10
15
Returns: 64
10
10
16
Returns: 74
10
10
17
Returns: 80
10
10
18
Returns: 82
10
10
19
Returns: 90
10
10
20
Returns: 96
10
10
21
Returns: 98
10
10
22
Returns: 112
10
10
23
Returns: 114
10
10
24
Returns: 120
10
10
25
Returns: 128
10
10
26
Returns: 130
10
10
27
Returns: 132
10
10
28
Returns: 136
10
10
29
Returns: 146
10
0
1
Returns: 1024
10
0
2
Returns: 2048
10
0
3
Returns: 3072
10
0
4
Returns: 4096
10
0
5
Returns: 5120
10
0
6
Returns: 6144
10
0
7
Returns: 7168
10
0
8
Returns: 8192
10
0
9
Returns: 9216
10
0
10
Returns: 10240
10
0
11
Returns: 11264
10
0
12
Returns: 12288
10
0
13
Returns: 13312
10
0
14
Returns: 14336
10
0
15
Returns: 15360
10
0
16
Returns: 16384
10
0
17
Returns: 17408
10
0
18
Returns: 18432
10
0
19
Returns: 19456
10
0
20
Returns: 20480
10
0
21
Returns: 21504
10
0
22
Returns: 22528
10
0
23
Returns: 23552
10
0
24
Returns: 24576
10
0
25
Returns: 25600
10
0
26
Returns: 26624
10
0
27
Returns: 27648
10
0
28
Returns: 28672
10
0
29
Returns: 29696
0
10
1
Returns: 1024
0
10
2
Returns: 2048
0
10
3
Returns: 3072
0
10
4
Returns: 4096
0
10
5
Returns: 5120
0
10
6
Returns: 6144
0
10
7
Returns: 7168
0
10
8
Returns: 8192
0
10
9
Returns: 9216
0
10
10
Returns: 10240
0
10
11
Returns: 11264
0
10
12
Returns: 12288
0
10
13
Returns: 13312
0
10
14
Returns: 14336
0
10
15
Returns: 15360
0
10
16
Returns: 16384
0
10
17
Returns: 17408
0
10
18
Returns: 18432
0
10
19
Returns: 19456
0
10
20
Returns: 20480
0
10
21
Returns: 21504
0
10
22
Returns: 22528
0
10
23
Returns: 23552
0
10
24
Returns: 24576
0
10
25
Returns: 25600
0
10
26
Returns: 26624
0
10
27
Returns: 27648
0
10
28
Returns: 28672
0
10
29
Returns: 29696
10
7
11
Returns: 52
8
8
6
Returns: 18
1
10
24
Returns: 4352
6
9
21
Returns: 128
3
1
19
Returns: 74
3
9
5
Returns: 74
3
5
29
Returns: 130
1
1
9
Returns: 18
1
6
15
Returns: 258
8
8
3
Returns: 8
0
0
4
Returns: 4
8
8
12
Returns: 48
6
4
23
Returns: 104
5
3
25
Returns: 112
8
1
3
Returns: 130
0
0
6
Returns: 6
7
2
18
Returns: 256
2
4
26
Returns: 106
3
3
20
Returns: 64
7
9
10
Returns: 40
5
3
24
Returns: 104
8
6
22
Returns: 112
4
5
18
Returns: 66
9
7
4
Returns: 10
5
4
4
Returns: 10
0
6
21
Returns: 1344
7
10
9
Returns: 40
7
8
15
Returns: 64
7
1
7
Returns: 208
10
4
4
Returns: 10
10
3
2
Returns: 4
1
9
17
Returns: 1666
7
1
21
Returns: 642
0
3
28
Returns: 224
5
3
14
Returns: 58
9
3
11
Returns: 184
5
0
26
Returns: 832
8
1
28
Returns: 1538
5
1
27
Returns: 288
4
2
25
Returns: 104
6
1
19
Returns: 336
10
5
10
Returns: 80
4
2
6
Returns: 24
7
10
19
Returns: 112
7
5
3
Returns: 8
8
1
7
Returns: 384
9
7
14
Returns: 64
10
1
2
Returns: 256
2
0
12
Returns: 48
4
4
3
Returns: 8
4
5
14
Returns: 52
7
8
18
Returns: 82
2
4
18
Returns: 74
9
6
8
Returns: 34
7
6
27
Returns: 120
3
4
19
Returns: 66
8
5
7
Returns: 32
7
9
23
Returns: 114
9
2
24
Returns: 866
2
3
22
Returns: 68
5
10
6
Returns: 34
0
2
27
Returns: 108
3
9
23
Returns: 408
10
3
12
Returns: 304
9
0
8
Returns: 4096
0
5
13
Returns: 416
0
1
22
Returns: 44
3
4
17
Returns: 58
2
1
9
Returns: 24
0
7
10
Returns: 1280
8
7
17
Returns: 80
9
7
1
Returns: 2
1
1
13
Returns: 26
4
1
1
Returns: 2
5
8
18
Returns: 98
2
9
2
Returns: 4
5
0
12
Returns: 384
7
2
25
Returns: 336
5
4
2
Returns: 4
0
1
25
Returns: 50
9
10
30
Returns: 152
10
9
17
Returns: 80
1
10
30
Returns: 5504