TopCoder problem "MarblesInABag" used in SRM 408 (Division II Level Three)



Problem Statement

    

Your friend Psycho Sid has challenged you to a game. He has a bag containing redCount red marbles and blueCount blue marbles. There will be an odd number of marbles in the bag, and you go first. On your turn, you reach into the bag and remove a random marble from the bag; each marble may be selected with equal probability. After your turn is over, Sid will reach into the bag and remove a blue marble; if there is no blue marble for Sid to remove, then he wins. If the final marble removed from the bag is blue, you will win. Otherwise, Sid wins.

Given the number of red and blue marbles in the bag, determine the probability that you win the game.

 

Definition

    
Class:MarblesInABag
Method:getProbability
Parameters:int, int
Returns:double
Method signature:double getProbability(int redCount, int blueCount)
(be sure your method is public)
    
 

Notes

-A return value with either an absolute or relative error of less than 1.0e-9 is considered correct.
 

Constraints

-redCount will be between 0 and 4000, inclusive.
-blueCount will be between 0 and 4000, inclusive.
-The sum of redCount and blueCount will be odd.
 

Examples

0)
    
1
2
Returns: 0.3333333333333333
Here you have a 1/3 chance of pulling out the red marble on your first turn. If you pull a blue marble, Sid will remove the other blue marble and you lose.
1)
    
2
3
Returns: 0.13333333333333333
Here you must remove both red marbles on consecutive pulls. This will happen 2/15 of the time.
2)
    
2
5
Returns: 0.22857142857142856
3)
    
11
6
Returns: 0.0
Here you can never win.
4)
    
4
11
Returns: 0.12183372183372182

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12180&pm=9754

Writer:

connect4

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Dynamic Programming