TopCoder problem "LastMarble" used in SRM 349 (Division I Level Three)



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 ints red and blue, the number of red and blue marbles initially in the bag. Before play begins, a friend removes several of the marbles from the bag, at random, without showing either of you, given in int removed.

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

0)
    
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)
    
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)
    
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.
3)
    
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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6067

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10673&pm=6067

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Advanced Math, Dynamic Programming