Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# methane/bt.py

Forked from sinya8282/bt.py
Created Apr 28, 2011
 #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." % sum(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(boards) sys.setrecursionlimit(scale+4) solver(length, boards, list())
to join this conversation on GitHub. Already have an account? Sign in to comment