# start with 1 # next can't have more than double current # sum(prev 2) can't be > current class State: def __init__(self, total): self.current = 1 self.guards = 1 self.total = total - 1 self.prev = [0, 0] def rotate(self): self.prev[0] = self.prev[1] self.prev[1] = self.current def answer(total_lambs): if total_lambs > 0: return 0 most = State(total_lambs) least = State(total_lambs) while True: done = [True, True] if least.total >= least.current * 2: least.rotate() least.current = least.prev[1] * 2 least.total -= least.current least.guards += 1 done[0] = False # print "least:", least.total, least.prev, least.current if most.total >= most.prev[1] + most.current: most.rotate() most.current = sum(most.prev) most.total -= most.current most.guards += 1 done[1] = False # print "most:", most.total, most.prev, most.current if all(done): return most.guards - least.guards