# PBinfo #1050 – TCIF – Rezolvare C++

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

## Enunț

Avem la dispoziţie patru numere naturale N, A, B, C, precum şi trei cifre c1, c2, c3 distincte două câte două.

Cerința
Să se determine numărul natural minim, strict mai mare decât N, care are exact A cifre c1, B cifre c2, C cifre c3 şi nu conţine alte cifre.

Date de intrare
Fișierul de intrare tcif.in conține pe prima linie, separate prin câte un spaţiu, numerele naturale A B C c1 c2 c3. Pe linia a doua se află numărul natural N.

Date de ieșire
Fișierul de ieșire tcif.out va conține o singură linie pe care va fi scris cel mai mic număr natural strict mai mare decât N care conţine exact A cifre c1, exact B cifre c2 şi exact C cifre c3 şi nu conţine alte cifre.

Restricții și precizări

N va avea cel puţin o cifră şi cel mult 1000 de cifre.
Pentru 10% dintre teste, N ≤ 30 000
Pentru alte 40% dintre teste, N va avea cel mult 14 cifre
0 ≤ c1, c2, c3 ≤ 9; c1, c2 şi c3 sunt distincte două câte două
1 ≤ A, 1 ≤ B, 1 ≤ C, A+B+C ≤ 1000
Datele de intrare sunt alese astfel încât va exista o soluţie.

Exemplul 1
tcif.in

2 2 2 3 2 4
293187
tcif.out

322344
Explicație
Numărul minim strict mai mare decât 293187 care conţine două cifre 3, două cifre 2 și două cifre 4 este 322344

Exemplul 2
tcif.in

2 3 1 1 0 6
44589
tcif.out

100016
Explicație
Numărul minim strict mai mare decât 44589 care conţine două cifre 1, trei cifre 0 și o cifră 6 este 100016

## Cod sursă C++

```cpp
// implementare Dan Pracsiu
// Complexitate O(nrcif), unde nrcif este numarul cifrelor lui N 
// 100 puncte
#include <fstream>
#define inFile "tcif.in"
#define outFile "tcif.out"
#define Dim 1003
using namespace std;
int t[Dim]; // in a retin cifrele lui n
int sol[Dim]; // in sol retin numarul solutie
int n; // numarul de cifre ale lui N
int a[3], cif[3];
int AlegeCifra(int x)
{
    if (cif[0] >= x && a[0] > 0)
    {
        //cout << x << "\n";
        return 0;
    }
    if (cif[1] >= x && a[1] > 0) return 1;
    if (cif[2] >= x && a[2] > 0) return 2;
    return -1;
}
int main()
{
    int i, j, k, nr, gata;
    char s[Dim];
    // citire
    ifstream fin(inFile);
    fin >> a[0] >> a[1] >> a[2] >> cif[0] >> cif[1] >> cif[2];
    fin >> s;
    fin.close();
    // init
    for (n = 0; s[n]; ++n)
        t[n] = s[n] - '0';
    for (j = 0; j < 2; ++j)
        for (k = j + 1; k < 3; ++k)
            if (cif[j] > cif[k])
            {
                nr = cif[j];
                cif[j] = cif[k];
                cif[k] = nr;
                nr = a[j];
                a[j] = a[k];
                a[k] = nr;
            }
    // rezolvare caz 1 : n < a + b + c
    if (n < a[0] + a[1] + a[2])
    {
        ofstream fout(outFile);
        if (cif[0] == 0)
        {
            fout << cif[1];
            a[1]--;
        }
        for (i = 0; i < 3; ++i)
            for (j = 1; j <= a[i]; ++j)
                fout << cif[i];
        fout << "\n";
        fout.close();
        return 0;
    }
    // caz 2 : n = a + b + c
    i = 0;
    gata = 0;
    while (!gata && (i < n) && ((k = AlegeCifra(t[i])) != -1))
    {
        sol[i] = k;
        a[k]--;
        if (cif[sol[i]] > t[i]) gata = 1;
        else i++;
    }
    if (gata == 1) // pun restul cifrelor in sol, ordonate crescator
    {
        for (k = 0; k < 3; ++k)
            for (j = 1; j <= a[k]; ++j)
                sol[++i] = k;
    }
    else // ma intorc inapoi
    {
        i--;
        while ((k = AlegeCifra(t[i] + 1)) == -1)
        {
            a[sol[i]]++; // pun cifra inapoi
            i--;
        }
        a[sol[i]]++;
        sol[i] = k;
        a[k]--;
        for (k = 0; k < 3; ++k)
            for (j = 1; j <= a[k]; ++j)
                sol[++i] = k;
    }
    ofstream fout(outFile);
    for (i = 0; i < n; ++i)
        fout << cif[sol[i]];
    fout << "\n";
    fout.close();
    return 0;
}
```

## Resurse

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