# PBinfo #4405 – unificare – Rezolvare C++

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

## Enunț

Prin operația de unificare a două numere naturale a și b înțelegem obținerea celui mai mare număr care se poate forma din cifrele distincte din scrierea numărului a și cifrele distincte din scrierea numărului b. De exemplu, unificând a = 727952 cu b = 92868 vom obține numărul 99876522, deoarece din a vom utiliza cifrele 2, 5, 7, 9, iar din b cifrele 2, 6, 8, 9. Cel mai mare număr pe care îl putem forma cu aceste cifre este 99876522.
Operația de unificare poate fi aplicată și pentru k numere, respectând aceeași regulă: pentru fiecare număr din cele k identificăm cifrele distincte care apar în scrierea lui, apoi determinăm cel mai mare număr care se poate forma utilizând toate aceste cifre. De exemplu, unificând numerele 112, 223 și 12334 vom obține 43322211.
Se dau două numere naturale, n și k, și un șir de n numere naturale a[1], a[2], …, a[n].

Cerința
Determinați și afișați:
1. cel mai mare număr de exact k cifre din șirul dat;
2. cel mai mare număr care poate fi obținut prin unificarea a două valori aflate pe poziții alăturate în șirul dat;
3. cel mai mare număr care se poate obține prin unificarea a k valori aflate pe poziții consecutive în șirul dat.

Date de intrare
Fișierul de intrare unificare.in conține pe prima linie un număr natural C, reprezentând cerința ce trebuie rezolvată (1, 2 sau 3), pe a doua linie n și k, cu semnificația din enunț, iar pe a treia linie cei n termeni ai șirului precizat, în ordinea
din șir. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire
În fișierul de ieșire unificare.out:
• dacă C = 1, se va afișa pe prima linie cel mai mare număr de k cifre din șirul dat;
• dacă C = 2, se va afișa pe prima linie cel mai mare număr obținut prin unificarea a două numere alăturate în șir;
• dacă C = 3, se va afișa pe prima linie valoarea maximă obținută prin unificarea a k valori aflate pe poziții consecutive.

Restricții și precizări

C ∈ {1, 2, 3}; 1 ≤ n ≤ 100.000; 1 ≤ k ≤ n / 2
0 ≤ a[i] ≤ 100.000.000, pentru oricare 1 ≤ i ≤ n
Pentru 20 de puncte, C = 1 și k ≤ 8
Pentru 5 de puncte, C = 2 și n = 2
Pentru 10 de puncte, C = 2 și 0 ≤ a[i] ≤ 9, pentru oricare 1 ≤ i ≤ n
Pentru 35 de puncte, C = 2, fără restricții suplimentare
Pentru 15 de puncte, C = 3 și k ≤ 8
Pentru 15 de puncte, C = 3 și k ≤ n / 2

Exemplul 1:
unificare.in

1
5 3
112 223 12334 561 289
unificare.out

561
Explicație
C = 1, n = 5 și k = 3. În șir sunt 4 numere care au exact 3 cifre: 112, 223, 561 și 289, cel mai mare dintre ele fiind 561.

Exemplul 2:
unificare.in

2
5 3
112 223 12334 561 289
unificare.out

6543211
Explicație
C = 2, n = 5 și k = 3, nu utilizăm valoarea lui k și unificând a[3] cu a[4] vom obține cea mai mare valoare: 6543211.

Exemplul 3:
unificare.in

3
5 3
112 223 12334 561 289
unificare.out

9865432211
Explicație
C = 3, n = 5 și k = 3. Cea mai mare valoare care se poate obține este 9865432211 și o obținem unificând a[3] cu a[4] și cu a[5].

## Cod sursă C++

```cpp
/*
Raluca Costineanu, Colegiul National Stefan cel Mare Suceava
*/
#include <fstream>
using namespace std;
ifstream f("unificare.in");
ofstream g("unificare.out");
const int N = 100005;
int main()
{
    int C, n, k, i, x;
    f >> C >> n >> k;
    if (C == 1)
    {
        int mx = 0;
        for (i = 1; i <= n; i++)
        {
            f >> x;
            int cx = x, nrcif = 0;
            do
                nrcif++, cx /= 10;
            while (cx);
            if (x > mx && nrcif == k)
                mx = x;
        }
        g << mx << '\n';
    }
    else if (C == 2)
    {
        int y, cx, cy;
        long long nr, mx = 0;
        f >> x;
        for (int i = 2; i <= n; i++)
        {
            f >> y;
            nr = 0;
            for (int c = 9; c >= 0; c--)
            {
                bool okX = 0, okY = 0;
                cx = x; cy = y;
                do
                {
                    if (cx % 10 == c)
                    {
                        okX = 1; break;
                    }
                    cx /= 10;
                } while (cx);
                do
                {
                    if (cy % 10 == c)
                    {
                        okY = 1; break;
                    }
                    cy /= 10;
                } while (cy);
                if (okX)nr = nr * 10 + c;
                if (okY)nr = nr * 10 + c;
            }
            if (nr > mx)mx = nr;
            x = y;
        }
        g << mx << '\n';
    }
    else if (C == 3)
    {
        int v[N], frMx[10] = {}, frK[10] = {};
        for (i = 1; i <= n; i++)
            f >> v[i];
        for (i = 1; i <= k; i++)
        {
            int fr[10] = {}, x = v[i];
            do
                fr[x % 10] = 1, x /= 10;
            while (x);
            for (int c = 0; c <= 9; c++)
                frK[c] += fr[c];
        }
        for (int c = 0; c <= 9; c++)
            frMx[c] = frK[c];
        for (i = k + 1; i <= n; i++)
        {
            int fr[10] = {}, x = v[i];
            do
                fr[x % 10] = 1, x /= 10;
            while (x);
            for (int c = 0; c <= 9; c++)
                frK[c] += fr[c];
            int fri[10] = {}, y = v[i - k];
            do
                fri[y % 10] = 1, y /= 10;
            while (y);
            for (int c = 0; c <= 9; c++)
                frK[c] -= fri[c];
            int sMX = 0, sK = 0, cmp = 0;
            for (int c = 0; c <= 9; c++)
                sMX += frMx[c], sK += frK[c];
            if (sK > sMX) cmp = 1;
            else if (sK < sMX) cmp = -1;
            else
            {
                for (int c = 9; c >= 0; c--)
                    if (frK[c] > frMx[c])
                    {
                        cmp = 1; break;
                    }
                    else if (frK[c] < frMx[c])
                    {
                        cmp = -1; break;
                    }
            }
            if (cmp > 0)
                for (int c = 0; c <= 9; c++)
                    frMx[c] = frK[c];
        }
        for (int c = 9; c >= 0; c--)
            while (frMx[c])
                g << c, frMx[c]--;
        g<<'\n';
    }
    return 0;
}
```

## Resurse

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