Untitled

from functools import lru_cache

# Zapamiętywanie wyników obliczeń
@lru_cache(None)
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    return lucas(n - 1) + lucas(n - 2)

def generowanie_ciagu_lucasa(limit): #Generuje ciąg Lucasa do wartości mniejszej niż maksymalna liczba w danych
    ciag_lucasa = []
    n = 0
    while True:
        value = lucas(n)
        if value > limit:
            break
        ciag_lucasa.append(value)
        n += 1
    return ciag_lucasa

def max_lucas_below(x, ciag_lucasa): #zwraca największą liczbę mniejszą lub równą x
    for value in reversed(ciag_lucasa):  # zaczynamy od największej liczby
        if value <= x:
            return value
    return 0

# Odczyt danych z pliku
with open('01.in', 'r') as file:
    dane = list(map(int, file.read().split()))
dane.pop(0)
print(dane)


# generujemy wszystkie elementy ciagu lucasa az do wartosci najwiekszej z pliku danych
max_value = max(dane)
ciag_lucasa = generowanie_ciagu_lucasa(max_value)

# Dla każdego elementu chcemy wyliczyć najkrótszą reprezentację
for element in dane:
    dlugosc_z_minusem = 0
    dlugosc_z_plusem = 0
    czy_znaleziono = False
    suma_wyrazow_ciagu_lucasa = 0
    x = element

    while not czy_znaleziono:
        najwieksza_mniejsza = max_lucas_below(x, ciag_lucasa)
        dlugosc_z_plusem += 1
        suma_wyrazow_ciagu_lucasa += najwieksza_mniejsza

        # Obliczamy resztę
        reszta = x - suma_wyrazow_ciagu_lucasa

        # Dopóki suma nie jest równa elementowi, kontynuujemy poszukiwania
        while reszta > 0:
            najwieksza_mniejsza_reszta = max_lucas_below(reszta, ciag_lucasa)
            dlugosc_z_plusem += 1
            suma_wyrazow_ciagu_lucasa += najwieksza_mniejsza_reszta
            reszta = reszta - najwieksza_mniejsza_reszta

        # Jeśli suma wyrazów jest równa elementowi, znaleziono odpowiednią reprezentację
        if suma_wyrazow_ciagu_lucasa == element:
            czy_znaleziono = True

    print(dlugosc_z_plusem)