Невозможная ошибка в программе, которая выравнивает богатство в группе (UVA 10137, «The Trip»)

Question

Я написал решение для this competitive programming problem. Он прошел все тестовые примеры, за исключением того, что он был отключен одним из последних случаев, и я не могу понять, почему. Проблема может быть сформулирована следующим образом: учитывая, сколько копеек каждый человек в группе имеет, сколько денег нужно переменить руками, чтобы все в группе были в пределах одной копейки друг от друга в богатстве?

Моя программа проста. Я изменил его, чтобы просто работать на массиве, сколько грошей у каждого есть:

def transfer(A): 
    A.sort(key = lambda x:-x) 
    extra = sum(A) % len(A) 
    average = sum(A) // len(A) 

    high = sum([abs(x - (average+1)) for x in A[:extra]]) 
    low = sum([abs(x - average) for x in A[extra:]]) 

    return (high+low)/2 

тест так, что он не на следующий:

print(transfer([613, 944, 7845, 8908, 12312, 22378, 27877, 54757, 55476, 90707, 91289, 178189])) 

Мой код говорит ответ 240710, в то время как «правильный» ответ - 240709. Где моя ошибка?

Answer 1

По-видимому, консенсус в том, что я получил другой ответ: я использую исключительно целочисленную арифметику, и их ответ использует арифметику float. Хотя их алгоритм был бы прав в бесконечной точности, выясняется, что в этом случае, по странной случайности, неточность float дает зачет. Это подтверждается gcc компилятором кода, который дает другой ответ, чем мой, но clang компиляция кода, который дает тот же ответ, который я нашел.

Answer 2

Проблема с программированием: Ваша задача состоит в том, чтобы вычислить из списка расходов минимальную сумму в размере денег, которые должны сменить руки, чтобы уравнять (в процентах) все расходы учащихся.

Это не то же самое, что и все, имеющие одинаковое богатство в пределах копейки. Это означает, что каждый обмен денег должен быть в пределах копейки. Плохая формулировка, с некоторой путаницей в интерпретации. Но пойдем с этим.

Существует пять человек, которые превышают среднюю величину 45941,25. Это люди, которые дают деньги другим. Но когда дается менее одного копейки, им не нужно давать этот дробный процент. Чтобы узнать, сколько людей не нужно сдать дополнительный цент:

extra = len([x for x in A if x > sum(A)/len(A)]) 

final = initial - difference. При проверке значения final находятся в пределах одного копейки.

initial = [178189, 91289, 90707, 55476, 54757, 27877, 22378, 12312, 8908, 7845, 944, 613] 
difference = [132247, 45347, 44765, 9534, 8815, -18064, -23563, -33629, -37033, -38096, -44997, -45328] 
final = [45942, 45942, 45942, 45942, 45942, 45941, 45941, 45941, 45941, 45941, 45940, 45940] 

пяти людей, у которых слишком много денег дают [132247, 45347, 44765, 9534, 8815] грошей прочь, раздавать в общей сложности 240708 cents. Кажется, это красиво.

Обратите внимание, что это меньшее значение, чем приведенное выше решение!