Code Sprint 2 - Coin Tosses

gistfile1.py

#!/usr/bin/env python

memo = {}
def calc(n, m):
    key = n * 10000 + m
    if key in memo:
        return memo[key]
    if n == 0 or n == m:
        res = 0
    elif m == 0:
        res = 2 ** (n + 1) - 2
    else:
        # Just to avoid max recursion depth error.
        if m + 1 == n:
            res = 2 ** n
        else:
            res = 1 + (calc(n, m + 1) + calc(n, 0)) / 2
    memo[key] = res
    return res

T = input()

for t in xrange(T):
    n, m = [int(i) for i in raw_input().split()]
    print "%d.00" % calc(n, m)