2026 - PlatouK: Diferență între versiuni
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2026/platouk - 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; pla...) |
Fără descriere a modificării |
||
Linia 33: | Linia 33: | ||
== Date de ieșire == | == 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 == | == Restricţii şi precizări == | ||
Linia 51: | Linia 52: | ||
: 1 | : 1 | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | |||
: Datele sunt introduse correct. | |||
: 4 | : 4 | ||
Linia 59: | Linia 62: | ||
def extract_plateau(a): | 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): | 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): | 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 | 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.") | |||
Versiunea de la data 27 aprilie 2023 19:00
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
# 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.")
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.