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

<syntaxhighlight lang="python" line>

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)

</syntaxhighlight>

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.