# PBinfo #3672 – Calculează pe n – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
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 ieșire
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. 

Restricții și precizări

1 ≤ n ≤ 1.000.000

Exemplu:
Intrare

1
Ieșire

0
Exemplu:
Intrare

5
Ieșire

3
Explicație
Prima dată se înmulțește 1 cu 2 și se obține 2, apoi se înmulțește cu 2 și se obține 4 apoi se adună cu 1 și se obține 5.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int v[1000001],a[1000001];
int main()
{
    int i,n,x,y,z;
    cin>>n;
    v[1]=0;
    v[2]=1;
    v[3]=1;
    for(i=4;i<=n;i++)
    {
     x=v[i-1];a[i]=i-1;
     if(i%2==0){y=v[i/2];
                if(y<x){a[i]=i/2;x=y;}
     }
     if(i%3==0){z=v[i/3];
                if(z<x){a[i]=i/3; x=z;}
     }
     v[i]=x+1;
    }
    cout<<v[n]<<endl;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3672)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3672/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3672/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)