COINTOSS - Coin Tosses

no tags 

 

You have an unbiased coin which you want to keep tossing till you get N consecutive heads. You've already tossed the coin M times already and surprisingly, all tosses resulted in heads. What is the expected number of tosses needed till you get N consecutive heads?
For example, if N = 2 and M = 0. You need to keep tossing the coin till you get 2 consecutive heads. It is not hard to show that on an average, 6 coin tosses are needed.
As another example, if N = 2 and M = 1. You need 2 consecutive heads and have already got 1. In your first toss, if you get get a heads, you are done. Otherwise, you need to keep tossing the coin till you get 2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0
Input:
The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.
Output:
Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places.
Constraints:
1 <= T <= 100
1 <= N <= 1000
0 <= M <= N
Sample Input:
4
2 0
2 1
3 3
3 2
Sample Output:
6.00
4.00
0.00
8.00
Explanation:
The first two samples are explained above. For the third case, you already have got 3 heads, so you do not need any more tosses.

 

You have an unbiased coin which you want to keep tossing till you get N consecutive heads. You've already tossed the coin M times already and surprisingly, all tosses resulted in heads. What is the expected number of tosses needed till you get N consecutive heads?

 

For example, if N = 2 and M = 0. You need to keep tossing the coin till you get 2 consecutive heads. It is not hard to show that on an average, 6 coin tosses are needed.

 

As another example, if N = 2 and M = 1. You need 2 consecutive heads and have already got 1. In your first toss, if you get get a heads, you are done. Otherwise, you need to keep tossing the coin till you get 2 consecutive heads. The expected number of coin tosses is thus 1 + (0.5 * 0 + 0.5 * 6) = 4.0

 

Input:

The first line contains the number of cases T. Each of the next T lines contains two numbers N and M.

 

Output:

Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places.

 

Constraints:

1 <= T <= 100

1 <= N <= 1000

0 <= M <= N

 

Sample Input:

4

2 0

2 1

3 3

3 2

 

Sample Output:

6.00

4.00

0.00

8.00

 

Explanation:

The first two samples are explained above. For the third case, you already have got 3 heads, so you do not need any more tosses.

 

 


hide comments
rajul: 2014-08-08 08:40:51

i'm loving python

Saurabh Jain: 2014-07-29 01:47:24

Getting the answers same as above but getting wrong answer for testcase 9 on the judge

Bhavik: 2014-02-18 11:59:48

same logic wa in C but ac in java..!! overflow in C is the reason..

Last edit: 2014-02-18 12:14:18
Aditya Pande: 2013-06-23 12:18:00

why WA
Edit:
got it

Last edit: 2013-06-23 12:23:15
jai_334: 2013-01-24 07:54:41

i am getting all ans correct as above mentioned in above comments like for test cases 20 15 , 1000 0 , 10 4
but still WA can any one help me out
....plz

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-13 20:05:06

got AC in 0.26s using PYTH 2.7 too ;-)

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-13 19:18:54

Finally AC in 0.00s after 18 attempts :-)

shubh_211: 2012-10-21 12:24:55

what's the answer for n = 1000 and m = 0
i am getting
2143017214372534641896850098120...5248773674411336138752.00
plz reply

Last edit: 2012-10-21 22:11:27
piyush agarwal: 2012-08-28 21:31:49

how to store value of pow(2.1000)??

piyush agarwal: 2012-08-28 21:30:38

how to store value of 2^1001 for the answer of 1000 0??


Added by:Varun Jalan
Date:2012-01-09
Time limit:0.678s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint 2 - InterviewStreet Contest