CodeSprint2 - Coin Toss

# A python implementation of a solution to the Coin Toss
# problem for Codesprint 2
# Author: Kevin Tham

def parseInput(inputString):
    inputList = map(int, inputString.split())
    N = inputList[0]
    M = inputList[1]
    return N, M

def solve(N, M=0):
    if M >= N:
        return 0
    elif M==0:
        # Reduce to original N consecutive heads problem
        return pow(2, N+1) - 2
    else:
        # Must toss 1 more + if we get heads + if we get tails
        return 1 + solve(N, M+1)/2 + solve(N, 0)/2

def main():
    for eachCase in xrange(int(raw_input())):
        N, M = parseInput(raw_input())
        print str(solve(N,M)) + ".00"

if __name__ == '__main__':
    main()