# def process_input done cur set last while last or in done new for val

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54``` ```def process_input(x,y,z,n): done = {} cur = set() last = [0] while last != [] or n in done: new = [] for val in last: if val < 0: if not val + x in done: done[val+x] = val new.append(val + x) if not val + y in done: done[val+y] = val new.append(val + y) if 0 <= val < n: if not val + x in done: done[val+x] = val new.append(val + x) if not val + y in done: done[val+y] = val new.append(val + y) if not val - z in done: done[val-z] = val new.append(val - z) if val > n: if not val - z in done: done[val-z] = val new.append(val - z) if val == n: steps = [val] while done[val] != 0: steps.append(done[val]) val = done[val] steps.append(0) steps.reverse() xs=ys=zs=0 for i in range(1,len(steps)): diff = steps[i] - steps[i-1] if diff == x: xs +=1 elif diff == y: ys +=1 elif diff == -z: zs +=1 else: assert False, "something fucked up" return ' '.join(map(str,[xs,ys,zs])) last = new return '-1' for input in open('input').readlines(): x,y,z,n = map(int, input.split()) print process_input(x,y,z,n) ```