Skip to content

Instantly share code, notes, and snippets.

@methane
Forked from sinya8282/bt.py
Created April 28, 2011 00:56
Show Gist options
  • Save methane/945584 to your computer and use it in GitHub Desktop.
Save methane/945584 to your computer and use it in GitHub Desktop.
#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())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment