http://googledevjp.blogspot.com/2011/04/google-code-jam-2011.html

bt.py

#http://googledevjp.blogspot.com/2011/04/google-code-jam-2011.html

def solve(rest, boards, counts):
    if boards == []:
        return rest == 0
    board = boards[-1]
    count = rest / board
    rest  = rest % board
    while count >= 0:
        if solve(rest, boards[0:-1], counts):
            counts.append(count)
            return True
        count -= 1
        rest  += board
    return False

def solver(length, boards, counts):
    if solve(length, boards, counts):
        answer = " + ".join(["%d*%d" % tuple(x) for x in zip(counts, boards)])
        print(answer + " == " + str(eval(answer)))
        print("Boards must have at least %d." % reduce(lambda x,y:x+y, counts))

if __name__ == "__main__":
    length = 10**10
    boards = sorted([233,456,787])
    solver(length, boards, list())
    # big(?) scale problem :) 1000 boards(1~100000 meters. Too unevenness?)
    import random
    import sys
    scale  = 10000
    boards = set()
    while len(boards) != scale:
        boards.add(int((100000-1)*random.random())+1)
    boards = sorted(list(boards))
    sys.setrecursionlimit(scale+4)
    solver(length, boards, list())