UVa 10328 - Coin Toss Solution

a=[]
def Main():
    try:
        while True:
            n,k=input().split()
            n=int(n)
            k=int(k)
            global a
            a=[None]*(n+1)
            a[0]=1
            i,j=1,1
            while j<k:
                i*=2
                a[j]=i
                j+=1
            for j in range(k,n+1):
                tmp=0
                for l in range(1,k+1):
                    tmp+=a[j-l]
                a[j]=tmp
            print(2**n-a[n])
    except EOFError:
        return 0
if __name__=='__main__':
    Main()