# PBinfo #2032 – Mmult – Rezolvare C++

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

## Enunț

Alexandru, mare informatician, a decis să își impresioneze prietenii cu următoarea problemă: Dându-se un vector cu N numere naturale nenule, se întreabă care este numărul minim de mulțimi cu numere consecutive de forma {1...K} în care acesta poate fi împărțit. Spre exemplu vectorul A = {1, 3, 2, 2, 1, 4} poate fi împărțit în număr minim de partiții astfel {1, 2, 3, 4}, {1, 2}.

Cerința
Cum această problemă a fost prea dificilă pentru prietenii săi, Alexandru te roagă pe tine să o rezolvi.

Date de intrare
Fișierul de intrare mmult.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații.

Date de ieșire
Fișierul de ieșire mmult.out va conține pe prima linie numărul S, reprezentând răspunsul problemei date de Alex.

Restricții și precizări

1 ≤ N ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000
dacă problema nu are soluție, se va afișa -1

Exemplu:
mmult.in

6
1 3 2 2 1 4
mmult.out

2

## Cod sursă C++

```cpp
//Todoran Alexandru Raul, clasa a V-a, Colegiul National Aurel Vlaicu Orastie.
#include <iostream>
#include <fstream>
using namespace std;
int n,a,x[1000002],i,s,mx,ok=1;
int main()
{
    ifstream fin ("mmult.in");
    ofstream fout ("mmult.out");
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a;
        x[a]++;
        if(a>mx)mx=a;
    }
    while(x[1])
    {
        i=1;
        while(x[i]){x[i]--;i++;}
        s++;
    }
    for(i=1;i<=mx;i++)if(x[i]){ok=0;break;}
    if(ok)fout<<s<<"\n";
    else fout<<"-1\n";
    return 0;
}
```

## Resurse

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