IITKWPCN - Playing With Balls

    There are W white balls and B black balls in a bag. A magician is performing tricks by drawing balls from the bag.

    In each step, the magician randomly removes any two balls from the bag. If the drawn balls are of the same color, he will put one white ball in the bag, otherwise he will put a black ball in it. The two drawn balls from the bag from the ball are discarded.

    He keeps on doing the above tricks until there is only one ball remaining in the bag.

    Given W and B, you have to determine the probability that the color of last ball remaining in the bag is black. You should print the answer with accuracy of upto 6 decimal digits.


    T : no of test cases (1 <= T <= 10^4)

    For every test case W and B  are given (0 <= W <= 10^8 and 0 <= B <= 10^8 and W + B != 0)


    For each test case, output the probability as stated in the problem statement.


1 1
1 2


hide comments
prabhat7298: 2019-08-17 21:18:07

Here is a formal proof for the solution:
No of balls N= W+B
There are only 3 possible actions and hence state transition
1. BB -> W+1, B-2
2. WW -> W-1, B
3. WB/Bw -> W-1,B
For last ball to be remaining black all the white balls and n-1 black balls should be consumed in N-1 trials(Since, at every trial one less ball remain in box therefore, after n-1 trail only one ball will remain)
Lets focus on white ball. Consider action 1 as success and actions 2&3 as failure for white ball. In every sucess one white ball increases in box and in every failure one white ball decreases.
For all white balls to vanish
Failure = W + Success
and we know Failure + Success = N-1
Solving these two eqns we'll get success = (B-1)/2
So, if B-1 is not divisible by 2 then all the white balls couldn't vanish.

satish18: 2019-02-06 12:12:53

observe pattern+if+else=AC

prabhav_123: 2018-12-15 20:44:44

no probability..lol ! one go,

mittalprateek: 2018-10-07 06:51:13

just observe the pattern ....you will get ac :{

touchstone: 2017-06-17 20:44:27

it's all about spending few minutes to analyze the question :) AC IN 1 GO :D

ace_cocytus: 2016-09-01 04:22:52

what a riddle

pankaj sharma: 2016-06-29 22:11:00

I solved the problem using observation,but I was trying to figure out the general formula for this. Was anyone able to get a general formula of the probability?

hash7: 2016-06-02 20:11:00

dont think as the problem setter wants you to think.. make some sample output and analyze it... you will get a 2 line logic :) nyc question

geoffreymace7: 2015-10-13 08:21:15

Nice question!

dwij28: 2015-09-08 18:46:33

Takes a bit of a time to understand, and then just 3 lines in python. :D

Added by:praveen123
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge