# PBinfo #3415 – VectorDiv – Rezolvare C++

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

## Enunț

Cerința
Se da un vector cu n elemente. Asupra fiecărui element putem efectua 2 tipuri de operații: să-l adunăm sau să-l scădem cu 1. La final, fiecare element trebuie să fie divizor al elementului următor. Adică, v[i] îl divide pe v[i + 1], oricare ar fi 1 ≤ i < n. Știind că ultimul element nu poate fi modificat, aflați numărul minim de operații pentru ca vectorul să îndeplinească condiția dată. 

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire
Programul va afișa pe ecran numărul minim de operații.

Restricții și precizări

1 ≤ n ≤ 10
cele n numere citite vor fi mai mici sau egale cu 1.000.000

Exemplu:
Intrare

4
2 8 4 10
Ieșire

5
Explicație
Un exemplu de vector care respectă condiția este 1 5 5 10.

## Cod sursă C++

```cpp
/// Solutie - Moca Andrei - 100p
#include <bits/stdc++.h>
using namespace std;
vector<int> v, st, d;
vector<vector<int>> vd;
int n, res(1e9), curr;
inline void Back(int k)
{
    if (k == 0 && res > curr)
        res = curr;
    if (curr >= res)
        return;
    for (const int& x : vd[st[k+1]])
    {
        st[k] = x;
        curr += abs(st[k] - v[k]);
        if (curr < res)
        	Back(k - 1);
        curr -= abs(st[k] - v[k]);
    }
}
int main()
{
    cin >> n;
    v = st = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> v[i];
    for (int i = v[n]; i; --i)
        if (v[n] % i == 0)
            d.emplace_back(i);
    vd = vector<vector<int>>(v[n] + 1);
    for (size_t i = 0; i < d.size(); ++i)
        for (size_t j = i; j < d.size(); ++j)
            if (d[i] % d[j] == 0)
                vd[d[i]].emplace_back(d[j]);
    st[n] = v[n];
    Back(n - 1);
    cout << res;
    return 0;
}
```

## Resurse

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