0142 - n3579 - Obtinere numar prin aplicare repetata de operatii

Cerința

Cunoscând numărul natural n,să se tipărească şirul de operaţii prin care se poate ajunge de la numărul iniţial 1 la numărul final n.

Date de intrare

Fişierul de intrare n311.in conţine pe prima linie valoarea numărului natural n.

Date de ieșire

Fişierul de ieşire n311.out va conţine pe prima linie şirul de operaţii format din numere întregi separate prin câte un spaţiu, cu semnificaţia de mai sus.

Restricții și precizări

1 < n <= 2 000 000000; Pot exista mai multe soluţii, se acceptă oricare, dacă se încadrează în timpul de execuţie; Nu este obligatorie folosirea tuturor tipurilor de operaţii.

Exemplul 1

n311in.txt

24

n311out.txt

1 1 3 -1 3

Exemplul 2

n311in.txt

4

n311out.txt

1 1 1

Rezolvare

#0142 - n3579 - Obtinere numar prin aplicare repetata de operatii
def verificare_restrictii(numar):    
    if 1 < numar <= 2 000 000000:    
        return True
    else:
        return False
def construieste_sir_operatii(n):
    sir_operatii = []

    while n != 1:
        sir_operatii.append(n)

        if n % 3 == 0:
            n //= 3
        elif (n - 1) % 3 == 0 and n != 4:
            n -= 1
        else:
            n *= 3

    sir_operatii.append(1)
    sir_operatii.reverse()

    return sir_operatii

with open("n311in.txt", "r") as file_in:
    n = int(file_in.readline().strip())

sir_operatii = construieste_sir_operatii(n)

with open("n311out.txt", "w") as fileout.txt:
    file_out.write(" ".join(map(str, sir_operatii)))