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

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
piyush agarwal: 2012-08-28 21:30:38

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

Pranshul Agarwal: 2012-06-30 05:16:26

@varun could you please check out my solution id 7236067..... everything is working fine.... even working for n=1000 m=0...
[EDIT] got my mistake... and got AC :)

Last edit: 2012-07-01 06:36:04
Pranshul Agarwal: 2012-06-20 05:01:20

@siddharth
your ans to 20 15 is correct...
you should check for overflow

Last edit: 2012-06-20 05:03:01
Sidharth Guglani: 2012-06-03 15:06:34

Dont know why i am getting WA
what is answer for 20 15
i m getting 2031616.00 is it correct?
Thanks in advance

experience257: 2012-01-27 10:16:13

@vratika 2016.00

Vratika Ghatiya: 2012-01-14 14:59:22

What will be the answer for 10 4..??

jitendra kumar: 2012-01-11 14:22:23

@Deepak :- I dont think so

BlackBird: 2012-01-10 06:11:36

time limit for languages other than C++ should be increased

Devil D: 2012-01-09 11:30:02

Does the answer fit in the Regular data types ?


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