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 numărul c, 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

Intrare

2

16

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

1

Ieșire

Datele nu corespund restricțiilor impuse.

Datele sunt introduse correct.

4

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 2026 - PlatouK

def extract_plateau(a): i = 0 max_len = 1 max_start = 0 while i < len(a): start = i while i < len(a) - 1 and a[i] == a[i+1]: i += 1 if i - start + 1 > max_len: max_len = i - start + 1 max_start = start i += 1 return a[max_start:max_start+max_len]

def longest_plateau(a, k): b = a.copy() max_plateau_len = 1 for _ in range(k): plateau = extract_plateau(b) if len(plateau) < 2: break max_plateau_len += len(plateau) - 2 b = [x for x in b if x not in plateau] return max_plateau_len

def most_frequent_plateau(a, k): b = a.copy() max_plateau_len = 1 most_frequent_plateau_value = a[0] for x in set(a): b = a.copy() max_current_plateau_len = 1 for _ in range(k): plateau = extract_plateau(b) if len(plateau) < 2: break if plateau[0] == x: max_current_plateau_len += len(plateau) b = [x for x in b if x not in plateau] else: b = [x for x in b if x not in plateau] if max_current_plateau_len > max_plateau_len: max_plateau_len = max_current_plateau_len most_frequent_plateau_value = x return most_frequent_plateau_value

if name == 'main': k = int(input()) n = int(input()) a = list(map(int, input().split())) p = int(input()) if p == 1: result = longest_plateau(a, k) else: result = most_frequent_plateau(a, k) if result is not None: print("Datele sunt introduse corect.") print(result) else: print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie Rezolvare

Citim datele de intrare: numărul de operații posibile k, numărul de elemente din șir n, șirul de numere a și cerința p. Implementăm o funcție longest_plateau(a, k) care primește ca argumente șirul a și numărul de operații posibile k și returnează lungimea maximă a unui platou care poate apărea în șir în urma efectuării celor două operații de maxim k ori. Implementăm o funcție most_frequent_plateau(a, k) care primește ca argumente șirul a și numărul de operații posibile k și returnează elementul din care este format platoul cu lungimea maximă care poate apărea în șir în urma efectuării celor două operații de maxim k ori. În funcția main, apelăm funcțiile implementate în funcție de cerința p și afișăm rezultatul.