b.py (710B) [raw]
1 #!/usr/bin/env python3 2 # In the "non-linear fuel cost" situation, we suddenly know 3 # the median is definitely not optimal. Consider 1,2,100. A 4 # median of 2 means you'd incur a huge penalty (100 + 99..) 5 # for the 100 term, 4851 to be exact (plus 1 more for the 1) 6 # 7 # A better solution is to optimize for the least number of 8 # far-out points by using the average. We see 34 is would 9 # give us 3300 instead, which is significantly better. 10 import sys 11 12 13 def cost(a, b): 14 # Distance 3 = 1 + 2 + 3 = sum(range(abs))) 15 return sum(range(abs(a - b) + 1)) 16 17 18 crabs = [] 19 for l in sys.stdin: 20 crabs = [int(x) for x in l.split(",")] 21 22 avg = round(sum(crabs) / len(crabs)) 23 24 print(sum([cost(x, avg) for x in crabs]))