Google Foobar Challenge (Python) - Glückliches LAMBS-Problem [geschlossen]

Question

Die Frage ist:

Ein Handlanger zu sein ist nicht nur eine Plackerei. Gelegentlich, wenn Commander Lambda sich großzügig fühlt, verteilt sie Lucky LAMBs (Lambdas Allzweck-Geldböcke). Handlanger können mit Lucky LAMBs Dinge wie ein zweites Paar Socken, ein Kissen für ihre Kojen oder sogar eine dritte tägliche Mahlzeit kaufen!

Es ist jedoch nicht einfach, LAMBs tatsächlich zu verteilen. Jeder Handlanger-Trupp hat eine strenge Rangfolge, die eingehalten werden muss - sonst revoltieren die Handlanger und Sie werden alle wieder zu Schergen zurückgestuft!

Es gibt 4 wichtige Regeln, die Sie befolgen müssen, um eine Revolte zu vermeiden:

1. Der jüngste Handlanger (mit dem geringsten Dienstalter) erhält genau 1 LAMB. (Es wird immer mindestens 1 Handlanger in einem Team sein.)
2. Ein Handlanger wird revoltieren, wenn die Person, die unmittelbar über ihnen steht, mehr als doppelt so viele LAMBs erhält wie sie.
3. Ein Handlanger wird revoltieren, wenn die Anzahl der LAMBs, die den nächsten beiden Untergebenen zusammen gegeben werden, größer ist als die Anzahl der LAMBs, die sie erhalten. (Beachten Sie, dass die beiden jüngsten Handlanger keine zwei Untergebenen haben, daher gilt diese Regel nicht für sie. Der zweitjüngste Handlanger würde mindestens so viele LAMBs erfordern wie der jüngste Handlanger.)
4. Es gibt immer mehr Handlanger zu bezahlen - der Commander hat viele Angestellte. Wenn noch genügend LAMBs übrig sind, sodass ein anderer Handlanger als der Älteste hinzugefügt werden kann, während die anderen Regeln eingehalten werden, müssen Sie diesen Handlanger immer hinzufügen und bezahlen.

Beachten Sie, dass Sie möglicherweise nicht alle LAMBs verteilen können. Ein einzelnes LAMB kann nicht unterteilt werden. Das heißt, alle Handlanger müssen eine positive ganzzahlige Anzahl von LAMBs erhalten.

Schreiben Sie eine Funktion namens solution (total_lambs), wobei total_lambs die ganzzahlige Anzahl von LAMBs in dem Handout ist, das Sie teilen möchten. Es sollte eine Ganzzahl zurückgegeben werden, die die Differenz zwischen der minimalen und der maximalen Anzahl von Handlangern darstellt, die die LAMBs teilen können (dh so großzügig wie möglich gegenüber denen sind, die Sie bezahlen, und so geizig wie möglich), während sie alle oben genannten Punkte befolgen Regeln, um eine Revolte zu vermeiden. Wenn Sie beispielsweise 10 LAMBs hatten und so großzügig wie möglich waren, konnten Sie nur 3 Handlanger (1, 2 und 4 LAMBs in der Reihenfolge des aufsteigenden Dienstalters) bezahlen, während Sie, wenn Sie so geizig wie möglich waren, 4 bezahlen konnten Handlanger (1, 1, 2 und 3 LAMBs). Daher sollte Lösung (10) 4-3 = 1 zurückgeben.

Um die Dinge interessant zu halten, variiert Commander Lambda die Größe der Lucky LAMB-Auszahlungen. Sie können erwarten, dass total_lambs immer eine positive ganze Zahl von weniger als 1 Milliarde (10 ^ 9) ist.

Mein Code:

def solution(total_lambs):
if total_lambs <= 10**9:
    return h_stin(total_lambs) - h_gen(total_lambs)
else: return 0

def h_gen(total_lambs):
x = 1
# I have directly used formulas for sum and nth term of GP instead of assigning them variables
while (2**x - 1) < total_lambs:
    x += 1
if (2**x - 1) <= total_lambs or 2**(x-2) + 2**(x-3) <= total_lambs - (2**(x-1) - 1):
    return x
else: return x-1

def h_stin(total_lambs):
if total_lambs == 1:
    return 1
if total_lambs == 2:
    return 2
arr = [1, 1]
for i in range(1,10**9):
    if sum(arr) < total_lambs:
        arr.append(arr[i] + arr[i-1])
    else: break
if sum(arr) <= total_lambs:
    return len(arr)
else: return len(arr) - 1

Wenn ich diesen Code in der Befehlszeile auf meinem PC ausführe, wird die korrekte Ausgabe zurückgegeben. Wenn ich ihn jedoch auf dem Foobar-Terminal überprüfe, wird für 9 der 10 Fälle Test fehlgeschlagen angezeigt. Kann mir jemand dabei helfen? Auch wenn mein Code falsch ist, erzähl mir bitte auch davon. Vielen Dank!!

Answer 1

Es scheint, dass Sie, wenn Sie großzügig sind, 1, 2, 4, 8, 16 auszahlen, damit n Handlanger 2**n - 1Einheiten erhalten.

Wenn Sie geizig sind, zahlen Sie 1, 1, 2, 3, 5, ... (können Sie Fibonacci sagen?) Aus, so dass m Handlanger die Summe von F (0), ..... F ( m - 1), was F (m + 1) - 1 ist.

Sie müssen also das größte n so 2 ** n - 1 <= lambsund das größte m so finden F(m + 1) - 1 <= lambs.

Dies ist eine Herausforderung für die Google-Codierung. Sie müssen den Code daher selbst schreiben.