# PBinfo #1655 – Platou – Rezolvare C++

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

## Enunț

Cerința
Fiind dat un şir de numere, denumim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem: 


platourile 1 1 1 şi 4 4 4  ambele având lungimea 3;
platourile 7 7  (cel care începe în poziţia a patra) şi 7 7 (cel care începe pe poziţia a zecea), ambele având lungimea 2;
platoul 3 care are lungimea 1.

În schimb nu avem platoul 7 7 7 7 deoarece cele patru elemente egale cu 7 nu sunt pe poziţii consecutive!

Se dă un şir de n numere. Fiecare dintre aceste numere aparţine intervalului [0,1000000]. Asupra acestui şir se pot efectua o singură dată următoarele două operaţiuni în această ordine: 


se extrage un platou la alegere;
se inserează platoul extras la pasul anterior într-o poziţie la alegere din şirul rezultat după extragere.

De exemplu, dacă avem următorul şir inițial: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8 extragem platoul 2 2 format din elementele aflate în penultima şi antepenultima poziţie şi obţinem şirul: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

În şirul rezultat inserăm platoul 2 2 (pe care l-am extras în pasul anterior) în poziţia a doua şi obţinem şirul: 2 2 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

Să se scrie un program care pentru un şir dat determină:


Lungimea maximă a unui platou din şirul dat iniţial precum şi valoarea cea mai mare a elementelor care formează un platou de lungime maximă.
Lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni precum şi valoarea cea mai mare a elementelor care ar putea forma un astfel de platou.

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


pe prima linie un număr natural V care poate avea valoarea 1 sau valoarea 2;
pe a doua linie un număr natual n;
pe a treia linie un şir de n numere naturale separate prin câte un spaţiu, reprezentând elementele şirului dat. Fiecare dintre aceste numere aparţine intervalului [0,1.000.000].

Date de ieșire
Fișierul de ieșire platou.out va conține:


dacă V=1, atunci pe această linie se vor scrie cele două numere care reprezintă răspunsul la prima cerinţă.
dacă V=2, atunci pe această linie se vor scrie cele două numere care reprezintă răspunsul la a doua cerinţă.

Restricții și precizări

1 ≤ n ≤ 1.000.000
numerele aparțin intervalului [0,1.000.000].
Pentru rezolvarea corectă a primei cerinţe se obţin 20 de puncte, iar pentru rezolvarea corectă a celei de a doua cerinţe se obţin 80 puncte.

Exemplu 1
platou.in

1
16 
2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
platou.out

3 9
Explicație
V=1, deci se rezolvă NUMAI prima cerinţă. Lungimea maximă a unui platou din şirul dat este 3. Sunt două astfel de platouri: 8 8 8 şi 9 9 9. Valoarea cea mai mare din care este format unul dintre aceste platouri este 9.

Exemplu 2
platou.in

2
16 
2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
platou.out

4 8
Explicație
V=2, deci se rezolvă NUMAI a doua cerinţă. În urma executării celor două operațiuni pot să apară platouri de lungime maximă 4 în două moduri: 2 2 2 2 respectiv 8 8 8 8. 

Valoarea cea mai mare din care este format unul dintre aceste platouri este 8.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
using namespace std;
int max1[1000001], max2[1000001],n,v;
ifstream  fin("platou.in");
ofstream fout("platou.out");
//ofstream fout("platou.out");
int lcrt=1,lmax,valmax,rezmax;
int x,y;
int main()
{
    fin >> v >> n;
    if (v==1)
    {
        fin >> x;
        for (int i=1;i<=n-1;i++)
        {
            fin >> y;
            if(x==y)
                lcrt++;
            else
                lcrt=1;
            //cout << y << lcrt << endl;
            if (lcrt > lmax)
            {
                lmax = lcrt;
                valmax = x;
            }
            else
                if (lmax == lcrt)
                    if (x > valmax)
                        valmax = x;
            x = y;
        }
//        cout << lmax << ' ' << valmax;
        fout << lmax << ' ' << valmax;
        return 0;
    }
    fin >> x;
    for (int i=1;i<=n-1;i++)
    {
        fin >> y;
        if(x==y)
            lcrt++;
        else
        {
            if (lcrt >= max1[x])
            {
                max2[x] = max1[x];
                max1[x] = lcrt;
            }
            else
                if (lcrt > max2[x])
                    max2[x] = lcrt;
            lcrt = 1;
        }
        x = y;
    }
    if (lcrt >= max1[x])
            {
                max2[x] = max1[x];
                max1[x] = lcrt;
            }
            else
                if (lcrt > max2[x])
                    max2[x] = lcrt;
    for (int i=1000000;i>=0;i--)
    {
        //if (max1[i]>0)
        //    cout << i << ' ' << max1[i] << ' ' << max2[i] << endl;
        if (max1[i]+max2[i]>rezmax)
        {
            rezmax = max1[i]+max2[i];
            valmax = i;
        }
    }
//    cout << rezmax << ' ' << valmax <<endl;
    fout << rezmax << ' ' << valmax <<endl;
    return 0;
}
```

## Resurse

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