MarblesInABag
SRM 408 · 2008-07-01 · by connect4
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.
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.
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.
2 3 Returns: 0.13333333333333333
Here you must remove both red marbles on consecutive pulls. This will happen 2/15 of the time.
2 5 Returns: 0.22857142857142856
11 6 Returns: 0.0
Here you can never win.
319 3000 Returns: 1.0789966341876459E-9
Very small (but non zero) probability of winning.
3999 4000 Returns: 0.0
Largest run time possible case currently.
Submissions are judged against all 109 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MarblesInABag with a public method double getProbability(int redCount, int blueCount) · 109 test cases · 2 s / 256 MB per case