#!/usr/bin/env python3 # In the "non-linear fuel cost" situation, we suddenly know # the median is definitely not optimal. Consider 1,2,100. A # median of 2 means you'd incur a huge penalty (100 + 99..) # for the 100 term, 4851 to be exact (plus 1 more for the 1) # # A better solution is to optimize for the least number of # far-out points by using the average. We see 34 is would # give us 3300 instead, which is significantly better. import sys def cost(a, b): # Distance 3 = 1 + 2 + 3 = sum(range(abs))) return sum(range(abs(a - b) + 1)) crabs = [] for l in sys.stdin: crabs = [int(x) for x in l.split(",")] avg = round(sum(crabs) / len(crabs)) print(sum([cost(x, avg) for x in crabs]))