# PBinfo #2136 – Peste – Rezolvare C++

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

## Enunț

Ursul: Bună, cumătră! Da cât peşte ai? Dă-mi şi mie, că tare mi-i poftă!
Vulpea: Ia mai pune-ţi pofta-n cui. Dacă vrei pește, du-te şi-ţi înmoaie coada-n baltă şi vei avea ce să mănânci.
Ursul: Învaţă-mă, te rog, cumătră, că eu nu ştiu cum se prinde peştele.
Vulpea: Alei, cumetre! da’ nu ştii că nevoia te-nvaţă ce nici nu gândeşti? Du-te deseară la baltă și bagă-ţi coada-n apă. Stai pe loc, fără să te mişti, până spre ziuă. Între timp, ia foaia aceasta pe care am scris N numere naturale și până dimineață trebuie să procedezi în felul următor:


elimini exact două cifre alăturate din fiecare număr scris pe foaie, astfel încât, celelalte cifre rămase după eliminare să formeze, de la stânga la dreapta, cel mai mare număr posibil (de exemplu, din numărul 77196, elimini cifrele 7 și 1 pentru a obține cel mai mare număr posibil 796).
toate cele N numere obținute la pasul anterior, le lipești unul după altul, în ce ordine vrei tu. Uitându-te de la stânga la dreapta la cifrele numerelor lipite, observi că s-a format un nou număr X. Ai grijă cum procedezi, căci până
dimineață, atâta pește se va prinde de coada ta cât vei obține tu valoarea lui X.

Ajutați-l pe urs să prindă cât mai mult pește posibil.

Cerința
Scrieți un program care citește N numere naturale și determină:


Cel mai mare număr de eliminări efectuate cu aceleași două cifre alăturate.
Cel mai mare număr natural X determinat astfel încât ursul să prindă cât mai mult pește.

Date de intrare
Fișierul de intrare peste.in conține pe prima linie numărul natural P care poate avea valoarea 1 sau 2 și reprezintă numărul cerinței. Cea de-a doua linie conține un număr natural N cu semnificaţia din enunţ, iar pe următoarele N linii, cele N numere scrise pe foaia ce i-a dat-o vulpea ursului, câte un număr natural pe fiecare linie a fișierului.

Date de ieșire
Fișierul de ieșire peste.out va conține pe prima linie un singur număr natural determinat conform cerinței problemei.

Restricții și precizări

1 ≤ n ≤ 100, fiecare dintre cele N numere au cel puțin 3 și cel mult 18 cifre;
pentru rezolvarea corectă a cerinţei 1 se acordă 40 de puncte, iar pentru rezolvarea corectă a cerinţei 2 se acordă
60 de puncte;
pentru cazul P=2, vor exista și teste în valoare de 25 de puncte în care cele N numere naturale au valori mai mici
decât 109 și alte teste în valoare de 10 puncte în care cele N numere din fișierul de intrare sunt mai mici decât 109 și au același număr de cifre.

Exemplul 1
peste.in

1
4
1791
802
777
77196
peste.out

2
Explicație
Se va rezolva cerința 1 și în fișier sunt patru numere cu care vom proceda astfel:


din 1791 eliminăm cifrele 1 și 7 iar numărul rezultat este 91
din 802 eliminăm cifrele 0 și 2 iar numărul rezultat este 8
din 777 eliminăm cifrele 7 și 7 iar numărul rezultat este 7
din 77196 eliminăm 7 și 1 iar numărul rezultat este 796

S-au efectuat două eliminări cu aceleași două cifre alăturate: 1 și 7.

Exemplul 2
peste.in

2
4
1791
802
777
77196
peste.out

9187967
Explicație
Cu aceleași patru numere din exemplul precedent, vom rezolva cerința 2.
În urma eliminărilor efectuate s-au obținut numerele: 91 8 7 796
Cel mai mare număr posibil, obținut prin lipirea acestor numere este 9187967.

## Cod sursă C++

```cpp
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
int maxi;
char c;
short int v[102][20],f[105],cerinta,n,d[25];
int maimare(int k1, int k2)//daca linia k1< linia k2 returneaza 1
{
short int N1=0,nr1[40],i;
for(i=1;i<=v[k1][0];i++)//lipesc k1k2 si obtin nr1
    if(v[k1][i]!=-1)
      nr1[++N1]=v[k1][i];
for(i=1;i<=v[k2][0];i++)
    if(v[k2][i]!=-1)
      nr1[++N1]=v[k2][i];
short int N2=0,nr2[40];//lipesc k2k1 si obtin nr2
for(i=1;i<=v[k2][0];i++)
    if(v[k2][i]!=-1)
      nr2[++N2]=v[k2][i];
for(i=1;i<=v[k1][0];i++)
    if(v[k1][i]!=-1)
      nr2[++N2]=v[k1][i];//compar nr1 si nr2 cifra cu cifra de la stanga la dreapta
i=1;
while(i<=N1)
    if(nr1[i]<nr2[i])
        return 1;
    else if(nr1[i]>nr2[i])
        return 0;
    else i++;
return 0;
}
void schimb_linia(int k1,int k2)
{   int l=max(v[k1][0],v[k2][0]);
	for(int j=0;j<=l;j++)
	  swap(v[k1][j],v[k2][j]);
}
void sortare_ptr_lipire()
{   int k1,k2;
    for(k1=1;k1<n;k1++)
        for(k2=k1+1;k2<=n;k2++)
            if(maimare(k1,k2)==1)
                schimb_linia(k1,k2);
}
void afisare()
{ int i,j;
	for(i=1;i<=n;i++)
   	for(j=1;j<=v[i][0];j++)
   	   if(v[i][j]!=-1) fout<<v[i][j];
   	fout<<'\n';
}
int main ()
{
   int i,j,k,m,p1,p2;
   long long x,cut,xmax;
    fin>>cerinta;
    fin>>n; fin.get();
    for(i=1;i<=n;i++)
    {
        j=1;
        while(1)
        {
            fin.get(c);
            if(c!='\n')
            {
                v[i][j]=c-'0';
                j++;
            }
            else
                break;
        }
        v[i][0]=j-1;
    }
    for(i=1;i<=n;i++)
        {
            for(j=1,xmax=0;j<=v[i][0]-1;j++)
            {
                for(k=1;k<=v[i][0];k++)
                    d[k]=v[i][k];
                m=v[i][0]-2;
                for(k=j;k<=m;k++)
                    d[k]=d[k+2];
                for(k=1,x=0;k<=m;k++)
                    x=x*10+d[k];
                if(x>xmax)
                {
                    xmax=x;
                    p1=j;p2=j+1;
                    if(v[i][j]>v[i][j+1])
                       cut=v[i][j]*10+v[i][j+1];
                    else
                      cut=v[i][j+1]*10+v[i][j];
                }
            }
            v[i][p1]=-1;v[i][p2]=-1;
            f[cut]++;
        }
        for(i=0,maxi=0;i<=99;i++)
            if(f[i]>maxi)
                maxi=f[i];
if(cerinta==1)
        fout<<maxi<<'\n';
    else
    {
      sortare_ptr_lipire();
      afisare();
    }
fin.close();
fout.close();
return 0;
}
```

## Resurse

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