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.

Exemplu 1

Intrare

n311.in

24

Ieșire

n311.out

1 1 3 -1 3

Exemplu 2

Intrare

n311.in

4

Ieșire

n311.out

1 1 1

Rezolvare

#0142 - n3579 - Obtinere numar prin aplicare repetata de operatii
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("n311.in", "r") as file_in:
    n = int(file_in.readline().strip())

sir_operatii = construieste_sir_operatii(n)

with open("n311.out", "w") as file_out:
    file_out.write(" ".join(map(str, sir_operatii)))