LastMarble
SRM 349 · 2007-05-15 · by erinn
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.
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.
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
Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LastMarble with a public method double winningChance(int red, int blue, int removed) · 74 test cases · 2 s / 256 MB per case