# PBinfo #4087 – vecine – Rezolvare C++

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

## Enunț

Se dă un șir de n cifre c1, c2, …, cn, adică 0 ≤ ci ≤ 9. Dintr-un șir de cifre se poate obține un șir de 1 ≤ m ≤ n numere a1, a2, …, am astfel: 


Inițial considerăm fiecare cifră un număr și obținem șirul de n numere ai = c1
Un număr nou poate fi obținut prin lipirea unei secvențe de două sau mai multe numere vecine din șirul original. Două elemente dintr-un șir se numesc vecine dacă acestea se regăsesc în șir pe poziții alăturate.
Operația de lipire de două sau mai multe numere se poate realiza de oricâte ori atât timp cât numărul obținut este mai mic sau egal cu 2.000.000.000, nu începe cu cifra 0 și există cel puțin două numere în șir.
De exemplu șirul [3, 5, 0, 2, 7, 3] poate deveni [35, 0, 2, 73] prin lipirea numerelor 3, 5 → 35 și 7, 3 → 73, care ulterior poate deveni [3502, 73] prin lipirea numerelor 35, 0, 2 → 3502. Dar nu putem crea șirul [35, 02, 73], deoarece am avea un număr care începe cu 0.

Două numere vecine sunt consecutive dacă primul este cu 1 mai mic decât al doilea.

Cerința
Cunoscându-se șirul de cifre inițial, să se obțină următoarele rezultate:


Presupunând că nu se face nici o lipire de cifre, fiecare cifră devenind un număr în șir, adică ai = c1, să se determine câte perechi de numere vecine consecutive există în șir;
Să se determine o modalitate de lipire a cifrelor astfel încât să se obțină cele mai mari două numere vecine consecutive și să se afișeze primul dintre aceste numere.

Date de intrare
Fișierul de intrare vecine.in conține pe prima linie două numere p și n, p reprezentând cerința 1 sau 2, iar pe linia următoare cele n cifre, despărțite prin câte un spațiu.

Date de ieșire
În fișierul de ieșire vecine.out se va afla un singur număr natural. Dacă p = 1, acesta va reprezenta răspunsul pentru cerința 1. Dacă p = 2, acesta va reprezenta răspunsul pentru cerința 2.

Restricții și precizări

Pentru cerința 2 se garantează că numerele ce se pot obține nu vor depăși valoarea 2.000.000.000
Tot pentru cerința 2 se garantează existența a cel puțin o pereche de numere vecine consecutive
Cifra 0 poate forma singură doar numărul 0.
Două numere vecine sunt consecutive dacă primul este cu 1 mai mic decât al doilea.
Pentru 20 de puncte p = 1 și 3 ≤ n ≤ 100.000
Pentru 80 de puncte p = 2 și 3 ≤ n ≤ 100.000

Exemplul 1:
vecine.in

1 18
3 2 1 2 1 0 6 3 0 5 6 3 0 6 9 2 9 3
vecine.out

2
Explicație
Există două perechi de numere vecine consecutive formate dintr-o singură cifră: 1, 2 și 5, 6

Exemplul 2:
vecine.in

2 18
3 2 1 2 1 0 6 3 0 5 6 3 0 6 9 2 9 3
vecine.out

6305
Explicație
Perechea cu cele mai mari două numere vecine consecutive este 6305 și 6306. Conform cerinței s-a scris în fișier doar primul număr din pereche.

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll nines[] = {9,99,999,9999,99999,999999,9999999,99999999,999999999};
bool exista(ll x){
    for(int i=0; i<9;i++){
        if (nines[i] == x)
        {
            return true;
        }
    }
    return false;
}
int main()
{
    ifstream cin("vecine.in");
    ofstream cout("vecine.out");
    string s;
    int p, n,k=0;
    char c;
    cin >> p >> n;
    for(int i=0;i<n;i++){
        cin >> c;
        s += c;
    }
    // CERINTA 1
    if (p==1)
    {
        for (int i = 1; i < n; i++)
        {
            if (s[i] == s[i-1]+1){
                // cout << i << " " << (int)s[i] << endl;
                k++;
            }
        }
        cout << k;
    }
    // CERINTA 2
    else{
        int maxx = 0;
        // cout << s;
        for(int m=1;m<=10;m++){
            for(int i=0;i<n-m;i++){
                // cout << s.substr(i+1,m+1);
                ll x = stoll(s.substr(i,m), nullptr, 10);
                ll y;
                if (exista(x))
                {
                    y = stoll(s.substr(i+m,m+1), nullptr, 10);
                }
                else {
                    y = stoll(s.substr(i+m,m), nullptr, 10);
                }
                // cout << x << " " << y << endl;
                if (x==y-1){
                    // cout << "!";
                    // k++;
                    if (maxx < x)
                    {
                        maxx = x;
                    }
                }
            }
            // cout << "----\n";
        }
        cout << maxx;
    }
    return 0;
}
```

## Resurse

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