Problem Statement
A bag is filled with a given quantity of red and blue marbles. In each turn, a
player reaches into the bag and removes 1, 2, or 3 marbles. The player looks to see
the color of the marbles, and announces how many of each color marble were removed. The last player to remove a red marble from the bag loses. You are given
Assuming you go first, and each player makes the optimal choice of number of marbles to remove, calculate the probability that you win the game.
Definition
- Class:
- LastMarble
- Method:
- winningChance
- Parameters:
- int, int, int
- Returns:
- double
- Method signature:
- double winningChance(int red, int blue, int removed)
- (be sure your method is public)
Notes
- Return value must be within 1e-9 absolute or relative error of the actual result.
Constraints
- red will be between 1 and 100, inclusive.
- blue will be between 1 and 100, inclusive.
- removed will be between 0 and red - 1, inclusive.
Examples
1
1
0
Returns: 0.5
Here, the best you can do is to select one marble. If you get the blue marble, then your opponent will get the red one, and you will win. You have a 50/50 chance.
1
2
0
Returns: 0.3333333333333333
Taking three marbles would guarantee a loss. Taking two marbles gives you a 1/3 chance of winning. If you take one marble, you have a 2/3 chance of getting a blue marble. Your opponent then takes one marble, with a 1/2 chance of getting the red marble (and you winning). 2/3 * 1/2 = 1/3. The best you can do here is a 1/3 chance of winning.
2
1
0
Returns: 0.6666666666666666
Once again, there's nothing to gain by taking all three marbles. Take two marbles, and you have a 2/3 chance of leaving the last red marble for your opponent. Take one marble, and you have a 2/3 chance of leaving your opponent with 1 red, 1 blue, and a 1/3 chance of leaving him with 2 red. Left with 1 and 1, your opponent takes 1 marble, and has a 50/50 shot of winning. Left with two reds, your opponent takes 1, and you definitely lose. Thus, you have only a 1/3 chance of winning by taking one marble initially. You take two marbles, and have a 2/3 chance of winning.
2
2
1
Returns: 0.5
Here, one of the four marbles has been removed, so we have to consider what to do when we aren't sure how many red and blue marbles remain in the bag.
2
2
0
Returns: 0.5
2
3
1
Returns: 0.5
100
80
43
Returns: 0.4216037078891402
62
100
61
Returns: 0.4994504504862716
13
54
12
Returns: 0.5000024219602255
82
11
8
Returns: 0.11817521401399665
9
88
7
Returns: 0.5000002259107094
13
13
10
Returns: 0.5386014268407592
85
81
4
Returns: 0.5764413967652542
64
22
7
Returns: 0.7472351111929894
65
83
20
Returns: 0.5185751124455752
96
12
10
Returns: 0.8889741569425456
86
31
3
Returns: 0.7421302778328819
24
57
23
Returns: 0.5000522970849155
97
75
73
Returns: 0.5845540351942131
51
9
0
Returns: 0.8524317274632858
86
59
55
Returns: 0.6091897261664498
80
100
46
Returns: 0.5121978695297171
78
44
31
Returns: 0.6497194757614986
41
11
5
Returns: 0.7896418621330925
40
29
9
Returns: 0.6036529019611552
16
56
2
Returns: 0.5061612336024184
83
91
66
Returns: 0.5218310463315513
20
20
7
Returns: 0.44732431189847655
95
5
50
Returns: 0.9500012618293173
57
43
32
Returns: 0.5897527114919747
98
99
9
Returns: 0.5549408716962372
100
99
55
Returns: 0.538811607390127
11
6
3
Returns: 0.6585326438267612
100
99
50
Returns: 0.46051427662540095
100
100
1
Returns: 0.5991135714248399
100
91
47
Returns: 0.5538946523677721
99
99
67
Returns: 0.5358956739211858
97
99
31
Returns: 0.46114625866018377
92
47
32
Returns: 0.6701217445821144
64
72
19
Returns: 0.46922254012169823
99
97
45
Returns: 0.5417278743133329
2
1
1
Returns: 0.6666666666666666
100
90
50
Returns: 0.5556434375451796
89
97
7
Returns: 0.5490389082233603
97
45
90
Returns: 0.6895963308978859
99
99
55
Returns: 0.5371934243880638
83
65
70
Returns: 0.5818289225880415
80
90
30
Returns: 0.5265547855427535
34
24
4
Returns: 0.6185907036904856
100
95
99
Returns: 0.543295133829118
100
99
23
Returns: 0.5458414709117274
89
45
67
Returns: 0.6721964691215772
43
23
12
Returns: 0.6606590541851276
100
100
99
Returns: 0.46611076490934306
98
99
97
Returns: 0.532127978872529
100
97
53
Returns: 0.5423598480282926
100
100
67
Returns: 0.46407275859308333
100
85
95
Returns: 0.5652234349709567
98
95
47
Returns: 0.5431138786479115
100
97
41
Returns: 0.544132855739659
99
100
93
Returns: 0.5323520244419836
100
100
20
Returns: 0.5461277302537406
100
95
90
Returns: 0.4564560792013996
100
80
35
Returns: 0.4208854408462597
10
15
4
Returns: 0.47801674029295527
100
100
50
Returns: 0.5379240275007613
95
92
76
Returns: 0.5405565613774832
25
5
9
Returns: 0.16649123545675287
100
17
96
Returns: 0.14501501783998333
89
79
53
Returns: 0.5576735547339124
100
1
99
Returns: 0.9900990099009901
32
25
9
Returns: 0.5895628928952114
100
99
30
Returns: 0.45633154203507437
100
99
15
Returns: 0.5506563357381343