Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Code Sprint 2 - Coin Tosses
#!/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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment