2026 - PlatouK

Sursa: - PlatouK

---

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

Dacă datele sunt introduse corect, pe ecran se va afișa: '"Datele sunt introduse corect.", apoi pe un rând nou 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., reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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

crescător

Exemplu 1

Intrare

2

16

2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2

1

Datele sunt introduse correct.

Ieșire

4

Exemplu 2

Intrare

2

5

3 3 3 4 4

1

Ieșire

Datele nu corespund restricțiilor impuse.

3

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 2026 - PlatouK

def find_longest_plateau(arr, k):

   n = len(arr)
   ans = 0
   ans_element = arr[0]

   for i in range(n):
       # Determina platoul curent
       j = i + 1
       while j < n and arr[j] == arr[i]:
           j += 1
       length = j - i

       # Calculeaza cate elemente se pot adauga inainte
       # sau dupa platou pentru a obtine un nou platou
       # cu elementele vechi
       extra = min(k, i, n-j)

       # Calculeaza lungimea noului platou
       new_length = length + 2 * extra

       if new_length > ans:
           ans = new_length
           ans_element = arr[i]

   return ans, ans_element

if __name__ == '__main__':

   k = int(input())
   n = int(input())
   arr = list(map(int, input().split()))
   question = int(input())

   if question == 1:
       print("Datele sunt introduse corect.")
       ans, _ = find_longest_plateau(arr, k)
       print(ans)
   elif question == 2:
       print("Datele sunt introduse corect.")
       _, ans_element = find_longest_plateau(arr, k)
       print(ans_element)
   else:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie Rezolvare

Am definit o funcție find_longest_plateau care primește un șir de numere și un număr k și returnează lungimea maximă a unui platou care poate să apară în șir în urma efectuării celor două operații de maxim k ori și elementul din care este format platoul. Pentru a determina lungimea maximă a unui platou, vom parcurge șirul și pentru fiecare poziție vom determina platoul curent, apoi vom calcula câte elemente se pot adăuga înainte sau după platou pentru a obține un nou platou cu elementele vechi, apoi vom calcula lungimea noului platou și o vom compara cu rezultatul curent, actualizând valoarea maximă și elementul corespunzător, dacă este cazul. În funcția main citim valorile de intrare și apoi verificăm valoarea întrebării. În funcție de întrebare, vom afișa lungimea maximă a unui platou sau elementul din care este format platoul, folosind funcția find_longest_plateau.