a.py (725B) [raw]
1 #!/usr/bin/env python3 2 # In a "all fuel is equal" situation, the optimal solution will 3 # be the median, since it's effectively the closest to the "middle" 4 # one can get. I forget the proof, but it works. Something like 5 # 6 # T = |x1 - m| + ... + |xi - m| 7 # 8 # If m is the median, there are i/2 points on each side. If m 9 # was NOT the median, it might get "closer" to a subset of points 10 # but the "larger" split will be >i/2 points, and it is getting 11 # "farther" from those points. The # of points farther > # closer, 12 # so it's a less optimal positioning. 13 import sys 14 15 crabs = [] 16 for l in sys.stdin: 17 crabs = [int(x) for x in l.split(",")] 18 19 s = sorted(crabs) 20 m = s[int(len(crabs) / 2)] 21 22 print(sum([abs(x - m) for x in crabs]))