Google Foobar Challenge (Python) - Problème Lucky LAMBS [fermé]

Question

La question est:

Être un homme de main n'est pas une corvée. De temps en temps, lorsque le commandant Lambda se sent généreux, elle distribue des Lucky LAMB (l'argent tout usage de Lambda). Les hommes de main peuvent utiliser les Lucky LAMB pour acheter des choses comme une deuxième paire de chaussettes, un oreiller pour leurs couchettes ou même un troisième repas quotidien!

Cependant, évincer les AGNEAU n'est pas facile. Chaque escouade d'hommes de main a un classement d'ancienneté strict qui doit être respecté - sinon les hommes de main se révolteront et vous serez tous rétrogradés en serviteurs!

Il y a 4 règles clés que vous devez suivre pour éviter une révolte:

1. L'homme de main le plus jeune (avec le moins d'ancienneté) obtient exactement 1 AGNEAU. (Il y aura toujours au moins 1 homme de main dans une équipe.)
2. Un homme de main se révoltera si la personne qui se classe immédiatement au-dessus d'eux obtient plus du double du nombre de LAMB qu'ils font.
3. Un homme de main se révoltera si le nombre de LAMB donnés à leurs deux prochains subordonnés combinés est supérieur au nombre de LAMB qu'ils reçoivent. (Notez que les deux hommes de main les plus juniors n'auront pas deux subordonnés, donc cette règle ne s'applique pas à eux. Le 2ème homme de main le plus junior aurait besoin d'au moins autant de LAMB que l'homme de main le plus junior.)
4. Vous pouvez toujours trouver plus d'hommes de main à payer - le commandant a beaucoup d'employés. S'il reste suffisamment de LAMB pour qu'un autre homme de main puisse être ajouté comme le plus ancien tout en obéissant aux autres règles, vous devez toujours ajouter et payer cet homme de main.

Notez que vous ne pourrez peut-être pas distribuer tous les LAMB. Un seul LAMB ne peut pas être subdivisé. Autrement dit, tous les hommes de main doivent obtenir un nombre entier positif de LAMB.

Écrivez une fonction appelée solution (total_lambs), où total_lambs est le nombre entier de LAMB dans le document que vous essayez de diviser. Il doit renvoyer un entier qui représente la différence entre le nombre minimum et maximum d'hommes de main qui peuvent partager les LAMB (c'est-à-dire être aussi généreux que possible envers ceux que vous payez et aussi avare que possible, respectivement) tout en obéissant à tout ce qui précède règles pour éviter une révolte. Par exemple, si vous aviez 10 LAMB et que vous étiez aussi généreux que possible, vous ne pouviez payer que 3 sbires (1, 2 et 4 LAMB, par ordre croissant d'ancienneté), alors que si vous étiez aussi avare que possible, vous pourriez payer 4 hommes de main (1, 1, 2 et 3 AGNEAUX). Par conséquent, la solution (10) doit renvoyer 4-3 = 1.

Pour garder les choses intéressantes, le commandant Lambda varie la taille des paiements Lucky LAMB. Vous pouvez vous attendre à ce que total_lambs soit toujours un entier positif inférieur à 1 milliard (10 ^ 9).

Mon 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

Lorsque j'exécute ce code en ligne de commande sur mon PC, il renvoie la sortie correcte, mais lorsque je le vérifie sur le terminal foobar, il indique Test Failed pour 9 des 10 cas. Quelqu'un peut il m'aider avec ça? Aussi, si mon code est erroné, veuillez m'en informer aussi. Merci!!

Answer 1

Il semble que lorsque vous êtes généreux, vous payez 1, 2, 4, 8, 16 pour que n homme de main reçoive des 2**n - 1unités.

Quand vous êtes radin, vous payez 1, 1, 2, 3, 5, ... (pouvez-vous dire Fibonacci?), Pour que m hommes de main obtiennent la somme de F (0), ..... F ( m - 1) qui est F (m + 1) - 1.

Il faut donc trouver le plus grand n tel que 2 ** n - 1 <= lambset le plus grand m tel que F(m + 1) - 1 <= lambs.

Il s'agit d'un défi de codage Google, vous devez donc écrire le code vous-même.