COINTOSS - Coin 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 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
nadstratosfer:
2019-11-29 04:15:57
Beware of absurd precision issues even in Python. |
|
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
|
|
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
|
|
(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
|
|
piyush agarwal:
2012-08-28 21:31:49
how to store value of pow(2.1000)?? |
Added by: | Varun Jalan |
Date: | 2012-01-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem used for CodeSprint 2 - InterviewStreet Contest |