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
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:
20140808 08:40:51
i'm loving python 

Saurabh Jain:
20140729 01:47:24
Getting the answers same as above but getting wrong answer for testcase 9 on the judge 

Bhavik:
20140218 11:59:48
same logic wa in C but ac in java..!! overflow in C is the reason.. Last edit: 20140218 12:14:18 

Aditya Pande:
20130623 12:18:00
why WA


jai_334:
20130124 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)(æ›¾æ¯…æ˜†):
20130113 20:05:06
got AC in 0.26s using PYTH 2.7 too ;) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130113 19:18:54
Finally AC in 0.00s after 18 attempts :) 

shubh_211:
20121021 12:24:55
what's the answer for n = 1000 and m = 0


piyush agarwal:
20120828 21:31:49
how to store value of pow(2.1000)?? 

piyush agarwal:
20120828 21:30:38
how to store value of 2^1001 for the answer of 1000 0?? 
Added by:  Varun Jalan 
Date:  20120109 
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 