# PBinfo #3087 – lego – Rezolvare C++

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

## Enunț

Crina și Rareș pornesc în călătoria imaginară spre Deva și pentru aceasta fiecare își construiește câte un autocar din piese de lego. Pentru a nu crea blocaje în trafic, intrarea autocarelor în oraș este gestionată de un semnal pe care este scris un număr natural S. Astfel, fiecare autocar ce ajunge în dreptul semnalului, trebuie să aștepte, un număr de minute egal cu valoarea absolută a diferenței dintre S și numărul de identificare al autocarului său. 

Cei doi copii își împart în mod egal piesele de lego pe care sunt scrise cifre (fiecare copil are același număr de piese ca și celălalt, pentru fiecare cifră în parte), cu care formează numerele de identificare ale celor două autocare. Crina aranjează una lângă alta toate piesele sale și formează cifră cu cifră, numărul N1 de identificare al autocarului ei iar Rareș procedează la fel și formează numărul N2 pentru autocarul său. Pentru ca cele două numere să nu fie identice, copiii stabilesc ca N1 să fie strict mai mic decât numărul S al semnalului, iar numărul N2 strict mai mare decât S. În cazul în care vreunul din cele două numere nu poate fi construit din piesele împărțite, atunci autocarul respectiv va avea identificatorul 0 și va aștepta la semnal până trece celălalt autocar.

Cerința
1. Determinați numerele N1 și N2 astfel încât, autocarul fiecărui copil să aștepte cât mai puține minute la semnal.
2. Știind că autocarele celor doi copii au ajuns în același timp în fața semnalului, determinați numărul  minim de  minute de așteptare ale autocarului care va trece primul de semnal. 

Date de intrare
Fișierul de intrare lego.in conține:

pe prima linie numărul natural C ce poate avea valorile 1 sau 2, reprezentând numărul cerinței;
pe cea de-a doua linie un singur număr natural S cu semnificația din enunț;
pe următoarele linii câte două numere naturale ni și ci, despărțite prin câte un spațiu, cu următoarea semnificație: ni reprezintă numărul pieselor cu cifra ci, pe care le are fiecare copil.


Date de ieșire
Pentru C = 1, fișierul de ieșire lego.out va conține pe prima linie două numere naturale N1 și N2, în această ordine, despărțite printr-un spațiu, determinate conform cerinței 1. 
Pentru C = 2, fișierul de ieșire lego.out va conține pe prima linie, un singur număr natural determinat conform cerinței 2. 

Restricții și precizări

1 ≤ S ≤ 1018;
fiecare copil are cel mult 19 piese;
cifrele ci sunt distincte;
pentru rezolvarea corectă a cerinței 1 se acordă 60 de puncte iar pentru rezolvarea corectă a cerinței 2 se acordă 40 de puncte.

Exemplul 1:
lego.in

1
153
1 7
3 4
lego.out

0 4447
Explicație
Se rezolvă doar cerința 1. Pe semnal este scris numărul 153. Fiecare copil are 3 piese cu cifra 4 și o piesă cu cifra 7. Crina nu poate construi cu aceste piese un număr mai mic decât 153, de aceea autocarul său este identificat cu numărul 0. Rareș construiește numărul N2 = 4447.

Exemplul 2:
lego.in

2
42
1 3
1 5
lego.out

7
Explicație
Se rezolvă doar cerința 2. Pe semnal este scris numărul 42. Fiecare copil are o cifră de 3 și o cifră de 5. Crina construiește  numărul N1 = 35 și așteaptă la semnal 42 - 35 = 7 minute. Rareș construiește numărul N2 = 53 și așteaptă la semnal 53 - 42 = 11 minute. Numărul minim al minutelor de așteptare este 7.

## Cod sursă C++

```cpp
#include<fstream>
using namespace std;
ifstream f("lego.in");
ofstream g("lego.out");
int v, nc1[10], nc2[10], nr[10], cif[10], ncif, nrcif;
unsigned long long S,n1,n2,dif;
unsigned long long construire_N2(unsigned long long m, int rep[]){
    unsigned long long nr=m;
    int i,j;
    for(i=9;i>=0;i--){
        for(j=1;j<=rep[i];j++){
            nr=nr*10+i;
        }
    }
    return nr;
}
int cifre(int v, int rep[]){
    int i;
    for(i=v+1;i<=9 && rep[i]==0;i++);
    return i;
}
int cifre2(int v, int rep[]){
    int i;
    for(i=v-1;i>=0 && rep[i]==0;i--);
    return i;
}
unsigned long long construire_N1(unsigned long long m, int rep[]){
    unsigned long long nr=m;
    int i,j,y;
    if(m==0){
        y=cifre(0,rep);
        nr=nr*10+y;
        rep[y]--;
    }
    for(i=0;i<=9;i++){
        for(j=1;j<=rep[i];j++){
            nr=nr*10+i;
        }
    }
    if(m==0)rep[y]++;
    return nr;
}
void nr_mic(unsigned long long z,int rep[], int cif){
    int y;
    unsigned long long x;
    y=cifre(cif,rep);
    if(y<10){
        rep[y]--;
        x=construire_N1(z*10+y,rep);
        rep[y]++;
        if(x<n2){
            n2=x;
        }
    }
}
void nr_mare(unsigned long long z,int rep[], int cif){
    int y;
    unsigned long long x;
    y=cifre2(cif,rep);
    if(y>=0){
        rep[y]--;
        x=construire_N2(z*10+y,rep);
        rep[y]++;
        if(x>n1){
            n1=x;
        }
    }
}
int main(){
    int xn, xc,ns,cifs[30],i;
    unsigned long long x,z;
    f>>v>>S;
    ncif=0;
    nrcif=0;
    while(f>>xn>>xc){
        nc1[xc]=xn;
        nc2[xc]=xn;
        nr[ncif]=xn;
        nrcif+=xn;
        cif[ncif]=xc;
        ncif++;
    }
    f.close();
    x=S;
    ns=0;
    do{cifs[ns]=x%10; ns++;x=x/10;}while(x!=0);
    if(nrcif<ns){
        n2=0;
    }
    else{
        if(nrcif>ns){n2=construire_N1(0,nc2);}
        else{
            n2=construire_N2(0,nc2);
            if(n2<=S){
                n2=0;
            }
            else{
                i=ns-1;
                nr_mic(0,nc2,cifs[i]);
                z=0;
                i=ns-1;
                while(i>=0 && nc2[cifs[i]]>0){
                    z=z*10+cifs[i];
                    nc2[cifs[i]]--;
                    i--;
                    if(i>=0){
                        nr_mic(z,nc2,cifs[i]);
                    }
                }
                if(i>=0){
                    nr_mic(z,nc2,cifs[i]);
                }
            }
        }
    }
    if(nrcif>ns){
        n1=0;
    }
    else{
        if(nrcif<ns){n1=construire_N2(0,nc1);}
        else{
            n1=construire_N1(0,nc1);
            if(n1>=S){
                n1=0;
            }
            else{
                i=ns-1;
                nr_mare(0,nc1,cifs[i]);
                z=0;
                i=ns-1;
                while(i>=0 && nc1[cifs[i]]>0){
                    z=z*10+cifs[i];
                    nc1[cifs[i]]--;
                    i--;
                    if(i>=0){
                        nr_mare(z,nc1,cifs[i]);
                    }
                }
                if(i>=0){
                    nr_mare(z,nc1,cifs[i]);
                }
            }
        }
    }
    if(v==1){
        g<<n1<<' '<<n2<<'\n';
    }
    else{
        if(n1==0){
            dif=n2-S;
        }
        else{
            if(n2==0){
                dif=S-n1;
            }
            else{
                if(S-n1<n2-S){
                    dif=S-n1;
                }
                else{
                    dif=n2-S;
                }
            }
        }
        g<<dif;
    }
    g.close();
    return 0;
}
```

## Resurse

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