Squished, improved.

checkpoint.py

#!/usr/bin/env python
import sys,math

k, x, d, t = 10000001 , [1,3,3,1] , {1:1,2:2,3:3}, 3

while len(x) > 3:
    i = reduce(lambda z,y: z if z > 0 else y[0] if y[1] > k else z, enumerate(x), -1)
    x,t = map(sum,zip([0]+x[0:i],x[0:i]+[0])) if i > 0 else map(sum,zip([0]+x,x+[0])), t+1
    for s in x: d[s] = t if s not in d else d[s]

f = lambda a: d[a] if a in d else a
g = lambda a,b: f(b)+f(a/b) if (a/b)*b == a else k

for r in range(1,int(sys.stdin.readline())+1):
    S = int(sys.stdin.readline())
    T = reduce(lambda z,y: min(z,g(S,y)),range(1,int(math.sqrt(S))+2),g(S,1))
    print "Case #"+str(r)+": "+str(T)

merge.py

#!/usr/bin/env python
import sys

l = None
s = lambda a: a if len(a) <= 1 else u(s(a[:len(a)/2]), s(a[len(a)/2:]))
c = lambda a: reduce(lambda x,y: (31*x + y) % 1000003,a,1)

def u(a,b):
    r = []
    while len(a) > 0 and len(b) > 0:
        if l.pop(0) == '1': r.append(a.pop(0))
        else:               r.append(b.pop(0))
    return r + a + b

for t in range(1,int(sys.stdin.readline())+1):
    n,l = int(sys.stdin.readline()), list(sys.stdin.readline().strip())
    a,b = s(range(n)), range(n)
    for i,v in enumerate(a): b[v] = i+1
    print "Case #"+str(t)+": "+str(c(b))

squished.py

#!/usr/bin/env python
import sys

f = sys.stdin.read().split()
v = lambda m,s: s[0] != '0' and 1 <= int(s) <= m 

def q(n):
    m, s = int(f[n*2]), f[n*2+1] ; a,b,c,d = 1,0,0,0
    for i in range(len(s)-1,-1,-1): # count backwards
        if v(m,s[i:i+1]): d += a
        if v(m,s[i:i+2]): d += b
        if v(m,s[i:i+3]): d += c
        a,b,c,d = d,a,b,0
    return a

for i in range(int(f.pop(0))): print "Case #"+str(i+1)+": "+str(q(i)%0xfaceb00c)