2073 - PlatouK v2

Sursa: - PlatouK v2

---

Cerinţa

Fiind dat un șir de numere, numim 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!

Asupra unui şir se poate efectua următoarea operaţiune:

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 citește un șir de n numere naturale din intervalul [0,10000] și un număr k și determină:

lungimea maximă a unui platou care poate să apară în şir în urma efectuării operaţiunii de mai sus de maxim k ori elementul din care este format platoul obținut după cele k operațiuni

Date de intrare

Programul va citi:

• pe prima linie un număr natural k;
• pe a doua linie un număr natural n;
• pe a treia linie un şir de n numere naturale separate prin câte un spaţiu.
• pe a patra linie p, care reprezinta cerința; p poate fi 1 sau 2

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
• pentru cerința 1 – 50% din punctaj
• pentru cerința 2 – 50% din punctaj
• dacă sunt mai multe platouri de lungime maxima se va afișa cel mai mare considera cel format din valoarea cea mai mare

toate testele au soluție

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. 2073 - PlatouK v2

def citire_lista():

   try:
       k = int(input())
       n = int(input())
       lista = list(map(int, input().split()))
       p = int(input())
       return k, lista, p
   except:
       print("Datele nu corespund restrictiilor impuse.")

def rezolva(k, lista):

   try:
       # calculam dictionarul frecventelor
       frecvente = {}
       for element in lista:
           frecvente[element] = frecvente.get(element, 0) + 1
       
       # gasim elementul cu cea mai mare frecventa
       max_frecventa = max(frecvente.values())
       element_max_frecventa = max(k for k, v in frecvente.items() if v == max_frecventa)
       
       # calculam lungimea maxima a unui platou dupa k operatii
       lungime_maxima = min(max_frecventa + k, len(lista))
       return lungime_maxima if p == 1 else element_max_frecventa
   except:
       print("Datele nu corespund restrictiilor impuse.")

def valideaza(valoare):

   try:
       if isinstance(valoare, int):
           print("Datele sunt introduse corect.")
           print(valoare)
       else:
           print("Datele sunt introduse corect.")
           print(*valoare)
   except:
       print("Datele nu corespund restrictiilor impuse.")

if __name__ == "__main__":

   k, lista, p = citire_lista()
   rezultat = rezolva(k, lista)
   valideaza(rezultat)

</syntaxhighlight>

Explicatie Rezolvare

Funcția citire_lista() primește datele de intrare și le citește folosind funcții predefinite în Python. Aceasta returnează un tuplu format din k, lista și p.

Funcția rezolva(k, lista) primește k și lista citite de la intrare și implementează algoritmul descris în cerință pentru a determina lungimea maximă a unui platou sau elementul din care este format platoul, în funcție de cerința specificată. Pentru a face acest lucru, funcția calculează mai întâi un dicționar al frecvențelor elementelor din lista și găsește elementul cu cea mai mare frecvență. Pentru a găsi lungimea