PROBLEMA 2026 de pe pbinfo- PlatouK. Va multumesc
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. 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 determina:
1: lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni de maxim k ori
2: elementul din care este format platoul
Date de intrare
Programul va citi:
pe prima linie un număr natural k;
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,10000].
pe a patra linie p, care reprezinta cerinta
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
numerele aparțin intervalului [0,10000].
pentru cerinta 1 – 50% din punctaj
pentru cerinta 2 – 50% din punctaj
daca sunt mai multe numere care au platou de lungime maxima se va afisa cel mai mare
toate testele au solutie
Răspunsuri la întrebare
Răspuns:
#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;
}
Explicație:
Vom afla pentru fiecare numar cele mai mari k secvente.