👤
a fost răspuns

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ăspuns :

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.

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că informațiile disponibile v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de sprijin, nu ezitați să ne contactați. Vă așteptăm cu drag și data viitoare! Nu uitați să adăugați site-ul nostru la favorite pentru acces rapid.


Wix Learning: Alte intrebari