Editing 3672 - Calculeaza pe n

== Cerinta ==

Se citește de la tastatură număr natural n. Pornind de la valoarea 1, asupra valorii curente x se pot aplica următoarele trei operații: înmulțire cu 2, înmulțire cu 3 sau adunare cu 1. De exemplu, dacă x=1 atunci se poate obține 2 (prin înmulțirea cu 2 sau prin adunarea cu 1) sau 3 (prin înmulțirea cu 3).

Calculați numărul minim de operații necesare pentru a obține numărul n începând de la numărul 1.

== Date de intrare ==

Programul citește de la tastatură numărul n.

== Date de iesire ==

Programul va afișa pe ecran numărul k, reprezentând numărul minim de operații pentru obținerea numărului n pornind de la 1 sau valoarea 0 dacă nu se poate obține n.

== Restrictii si precizari ==

*1 ≤ n ≤ 1.000.000

== Exemplul 1 ==
;Intrare
:1
;Iesire
;Datele introduse corespund restrictiilor impuse
:0

== Exemplul 2 ==
;Intrare
:0
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def min_operatii(n):
    visited = set()
    queue = deque([(1, 0)])  # Coada va conține tupluri (valoare_curenta, numar_operatii)

    while queue:
        x, k = queue.popleft()

        if x == n:
            return k

        if x * 2 not in visited and x * 2 <= n:
            queue.append((x * 2, k + 1))
            visited.add(x * 2)

        if x * 3 not in visited and x * 3 <= n:
            queue.append((x * 3, k + 1))
            visited.add(x * 3)

        if x + 1 not in visited and x + 1 <= n:
            queue.append((x + 1, k + 1))
            visited.add(x + 1)

    return 0  # Nu s-a putut ajunge la n

# Citirea datelor de intrare
n = int(input("Introduceți numărul n: "))

# Calculul și afișarea rezultatului
rezultat = min_operatii(n)
print(f"Numărul minim de operații pentru a obține {n} este {rezultat}.")

</syntaxhighlight>