Fehler in einem Programm, das Reichtum in einer Gruppe ausgleicht (UVA 10137, "The Trip")

Question

Ich habe eine Lösung für this competitive programming problem geschrieben. Es hat alle Testfälle bestanden, außer dass es für den letzten Fall um eins ging, und ich kann nicht herausfinden warum. Das Problem kann wie folgt ausgedrückt werden: Wie viele Cent muss jede Person in einer Gruppe haben, wie viel Geld muss sie wechseln, damit jeder in der Gruppe innerhalb eines Pennys in Reichtum ist?

Mein Programm ist einfach. Ich änderte es für den Betrieb nur auf eine Reihe von, wie viele Pfennige jeder hat:

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 

Der Testfall, dass es nicht auf die folgenden:

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

Mein Code sagt, die Antwort ist 240710, während Die "richtige" Antwort ist 240709. Wo ist mein Käfer?

Answer 1

Der Konsens scheint zu sein, dass der Grund, warum ich eine andere Antwort bekam, ist, dass ich ausschließlich ganzzahlige Arithmetik verwende und ihre Antwort Float-Arithmetik verwendet. Während ihr Algorithmus in unendlicher Genauigkeit korrekt sein würde, stellt sich heraus, dass in diesem Fall, durch einen seltsamen Zufall, die Ungenauigkeit des Floats einen "Off-by-One" ergibt. Dies wird durch gcc kompiliert Code, der eine andere Antwort gibt als meine, aber clang kompilieren Code, der die gleiche Antwort gibt, die ich gefunden habe.

Answer 2

Die Programmierung Problem Staaten: Ihre Aufgabe ist es, aus einer Liste von Ausgaben, die Mindestmenge von Geld, die Hände ändern müssen, um (innerhalb eines Cent) alle Studenten Kosten ausgleichen zu berechnen.

Das ist nicht dasselbe wie jeder, der den gleichen Reichtum in einem Penny hat. Es bedeutet, dass jeder Geldwechsel in einem Penny sein sollte. Schlechte Formulierung, mit einiger Verwirrung über die Interpretierbarkeit. Aber lass uns damit gehen.

Es gibt fünf Leute, die über dem Durchschnittswert von 45941,25 liegen. Sie sind die Leute, die den anderen das Geld geben. Aber wenn es weniger als einen Cent gibt, müssen sie diesen Bruchteil-Cent nicht geben. Um herauszufinden, wie viele Menschen brauchen keine zusätzlichen Cent zu übergeben:

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

final = initial - difference. Bei der Überprüfung liegen die final Werte innerhalb des einen Penny-Kriteriums.

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] 

Die fünf Menschen, die zu viel Geld haben, geben [132247, 45347, 44765, 9534, 8815] Pennies weg, so dass insgesamt 240708 cents entfernt. Es scheint gut zu harmonieren.

Beachten Sie, dass es sich um einen niedrigeren Wert als die oben angegebene Lösung handelt!