# PBinfo #2073 – PlatouK_v2 – Rezolvare C++

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

## Enunț

Fiind dat un șir de numere, numim 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!

Asupra unui şir se poate efectua următoarea operaţiune:


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.

Cerința
Să se scrie un program care citește un șir de n numere naturale din intervalul [0,10000] și un număr k și determină:


lungimea maximă a unui platou care poate să apară în şir în urma efectuării operaţiunii de mai sus de maxim k ori
elementul din care este format platoul obținut după cele k operațiuni

Date de intrare
Programul va citi:


pe prima linie un număr natural k;
pe a doua linie un număr natural n;
pe a treia linie un şir de n numere naturale separate prin câte un spaţiu.
pe a patra linie p, care reprezinta cerința; p poate fi 1 sau 2

Date de ieșire
Programul va afisa lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni de maxim k ori sau elementul din care este format platoul.

Restricții și precizări

1 ≤ n ≤ 1000000
1 ≤ k ≤ 100
pentru cerința 1 – 50% din punctaj
pentru cerința 2 – 50% din punctaj
dacă sunt mai multe platouri de lungime maxima se va afișa cel mai mare considera cel format din valoarea cea mai mare
toate testele au soluție

Exemplul 1
Intrare

2
16 
2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
1 
Iesire

4
Exemplul 2
Intrare

2
16 
2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
2
Iesire

8
Explicație
Î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.

## Cod sursă C++

```cpp
/// Solutie - Moca Andrei - 100p
#include <bits/stdc++.h>
using namespace std;
int n, k, maxi, a[10001][103], l, x, y, smax = -1, elem = -1, s, cerinta;
void proces(int nr)
{
    int aux = a[nr][a[nr][0]];
    int j = a[nr][0]-1;
    while (aux > a[nr][j] && j)
        a[nr][j+1] = a[nr][j], j--;
    a[nr][j+1] = aux;
    while (a[nr][0] > k)
        a[nr][0]--;
}
int main()
{
    cin >> k >> n >> x;
    maxi = x;
    for (int i = 2; i <= n; i++)
    {
        cin >> y;
        maxi = max(maxi, y);
        if (x == y)
            l++;
        else
        {
            a[x][0]++;
            a[x][a[x][0]] = l;
            proces(x);
            l = 1;
        }
        x = y;
    }
    a[x][0]++;
    a[x][a[x][0]] = l;
    proces(x);
    for (int i = 0; i <= maxi; i++)
    {
        s = 0;
        for (int j = 1; j <= a[i][0]; j++)
            s += a[i][j];
        if (s >= smax)
            smax = s, elem = i;
    }
    cin >> cerinta;
    if (cerinta == 1)
        cout << smax;
    else
        cout << elem;
    return 0;
}
```

## Resurse

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