0139 - n311 - Obtinere numar prin aplicare repetata de operatii

Enunt

Pornind de la numărul 1,orice număr natural se poate obţine aplicând repetat în mod convenabil operaţii din cele de mai jos:

• înmulţire cu 3
• adunare cu 1
• scădere cu 1

De exemplu numărul 24 se poate obţine astfel:

Adunăm 1: 1 + 1 = 2 Adunăm 1: 2 + 1 = 3 Înmultim cu 3: 3 * 3 = 9 Scădem 1: 9 - 1 = 8 Înmulțim cu 3: 8 * 3 = 24

Urmărind operaţiile de la stânga la dreapta pentru exemplul de mai sus, şirul de operaţii se codifică cu 1, 1, 3, -1, 3.

Cerinta

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 n311in.txt conţine pe prima linie valoarea numărului natural n.

Date de iesire

Fişierul de ieşire n311out.txt 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.

Restrictii si precizari

• 1 ⩽ n %les; 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

Datele introduse corespund restrictiilor impuse

1 1 3 -1 3

Exemplul 2

n311in.txt

-121

Datele introduse nu corespund restrictiilor impuse

Rezolvare

def verifica_restrictii(n):
    return 1 <= n <= 2000000000

def generare_sir_operatii(n):
    operatii = []

    def backtracking(current, target):
        if current == target:
            return True
        if current > target:
            return False

        # Încercăm să adunăm 1
        if backtracking(current + 1, target):
            operatii.append(1)
            return True

        # Încercăm să scădem 1
        if backtracking(current - 1, target):
            operatii.append(-1)
            return True

        # Încercăm să înmulțim cu 3
        if backtracking(current * 3, target):
            operatii.append(3)
            return True

        return False

    # Apelăm funcția de backtracking
    backtracking(1, n)

    return operatii

# Citire din fișierul de intrare
with open('n311in.txt', 'r') as file:
    n = int(file.readline())

# Verificare restricții
if verifica_restrictii(n):
    # Generare și afișare șir de operații
    operatii = generare_sir_operatii(n)

    # Scriere în fișierul de ieșire
    with open('n311out.txt', 'w') as file_out:
        file_out.write(" ".join(map(str, operatii)))
else:
    print("Date de intrare nevalide.")