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.
Rezolvare
Rezolvare ver. 1
# 2026 - PlatouK
def validate_input(k, n, sequence):
# Verifică dacă datele de intrare sunt corecte
if not 1 <= k <= 100 or not 1 <= n <= 1000000 or not all(0 <= x <= 10000 for x in sequence):
return False
return True
def find_longest_plateau(k, sequence):
longest_plateau_length = 0
longest_plateau_element = None
for i in range(len(sequence)):
# Verifică dacă putem efectua operațiunea de extragere/inserare de cel puțin o dată
if k >= i:
# Extrage platoul din secvență
plateau = []
j = i
while j < len(sequence) and (not plateau or sequence[j] == plateau[0]):
plateau.append(sequence[j])
j += 1
plateau_length = len(plateau)
# Verifică dacă putem efectua operațiunea de extragere/inserare de cel puțin încă o dată
if k >= i + plateau_length:
# Inserează platoul în secvență și calculează lungimea platoului rezultat
new_sequence = sequence[:i] + sequence[i+plateau_length:]
for l in range(i, len(new_sequence)):
new_sequence.insert(l, plateau[0])
k_left = k - (i + plateau_length)
while k_left >= l + plateau_length:
new_sequence = new_sequence[:l+plateau_length] + plateau + new_sequence[l+plateau_length:]
k_left -= (l + plateau_length)
result_plateau = []
j = 0
while j < len(new_sequence):
# Calculează lungimea platoului format din elementul curent
plateau = []
while j < len(new_sequence) and (not plateau or new_sequence[j] == plateau[0]):
plateau.append(new_sequence[j])
j += 1
plateau_length = len(plateau)
# Verifică dacă lungimea platoului este maximă
if plateau_length > longest_plateau_length:
longest_plateau_length = plateau_length
longest_plateau_element = plateau[0]
# Continuă căutarea în secvența următoare
j += 1
return longest_plateau_length, longest_plateau_element
if __name__ == "__main__":
# Citire date de intrare
k = int(input())
n = int(input())
sequence = list(map(int, input().split()))
p = int(input())
# Verificare date de intrare
if not validate_input(k, n, sequence):
print("Datele nu corespund restricțiilor impuse.")
else:
# Calculează lungimea maximă a platoului sau elementul din care este format platoul
longest_plateau_length, longest_plateau_element = find_longest_plateau(k, sequence)
if p == 1:
print("Datele sunt introduse corect.")
print(longest_plateau_length)
else:
print("Datele sunt introduse corect.")
print(longest_plateau_element)
Explicatie Rezolvare
Funcția validate_input(k, n, sequence) verifică dacă datele de intrare respectă restricțiile impuse în enunțul problemei. Aceasta primește ca parametrii: k, numărul limită de operații de inserare și extragere, n, numărul de elemente din secvență și sequence, secvența de numere. Funcția returnează True dacă datele respectă restricțiile și False altfel.
Funcția find_longest_plateau(k, sequence) primește ca parametrii k, numărul limită de operații de inserare și extragere și sequence, secvența de numere. Aceasta determină lungimea maximă a unui platou sau a elementului din care este format platoul din secvență, folosind metoda de inserare și extragere descrisă în enunțul problemei. Funcția returnează o tuplă formată din lungimea maximă a platoului și elementul din care este format platoul.
În funcția main(), se citesc datele de intrare și se validează cu ajutorul funcției validate_input(). Dacă datele sunt corecte, se calculează lungimea maximă a platoului sau elementul din care este format platoul folosind funcția find_longest_plateau(). Dacă parametrul p este egal cu 1, se afișează lungimea maximă a platoului, altfel se afișează elementul din care este format platoul.
