2840 - Secventa Uniforma

Cerinţa

Numim secvență uniformă a unui șir de numere naturale un subșir al acestuia, format din termeni cu aceeași valoare, aflați pe poziții consecutive în șirul dat. Lungimea secvenței este egală cu numărul de termeni ai acesteia.

Se dă un șir de cel puțin două și cel mult 1000000 de numere naturale din intervalul [0,10^9]. În șir există cel puțin doi termeni egali pe poziții consecutive. Se cere să se determine o secvență uniformă de lungime maximă în șirul dat și să se afișeze pe lungimea acestei secvențe și termenii acesteia. Dacă sunt mai multe astfel de secvențe, se afișează doar termenii ultimei dintre acestea.

Date de intrare

Fișierul de intrare secventauniforma.in conține pe prima linie un șir de cel puțin două și cel mult 1000000 de numere naturale din intervalul [0,10^9], separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",fișierul de ieșire secventauniforma.out va conține pe prima linie lungimea acestei secvențe și, pe o linie nouă, separați prin câte un spațiu, termenii acesteia.. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei necesare și al timpului de executare.
• Se recomandă evitarea memorării elementelor șirului într-un tablou sau în altă structură de date similară.

Exemple

Exemplul 1

secventauniforma.in

1 1 1 1 1 1 1 1 1 1

secventauniforma.out

Datele sunt introduse corect.

10

1 1 1 1 1 1 1 1 1 1

Exemplul 2

secventauniforma.in

5 5 5 5 5 5 5 5

secventauniforma.out

Datele sunt introduse corect.

8

5 5 5 5 5 5 5 5

Exemplul 3

secventauniforma.in

2 3 1000000001

iesire

Datele nu corespund restricțiilor impuse.

secventauniforma.out

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 2840 - Secventa Uniforma

def valideaza_intrare(lst: list[int]) -> bool:

   """
   Verifică dacă datele de intrare sunt valide conform cerințelor.
   """
   if not (2 <= len(lst) <= 10 ** 6):
       return False
   for i in range(1, len(lst)):
       if lst[i] < 0 or lst[i] > 10 ** 9 or lst[i] != lst[i - 1]:
           return False
   return True

def gaseste_secventa_uniforma(lst: list[int]) -> tuple[int, list[int]]:

   """
   Găsește cea mai lungă secvență uniformă în șirul dat.
   """
   if not valideaza_intrare(lst):
       return 0, []
   lungime_maxima = 1
   termeni_maximi = [lst[0]]
   lungime_curenta = 1
   termeni_curenti = [lst[0]]
   for i in range(1, len(lst)):
       if lst[i] == lst[i - 1]:
           lungime_curenta += 1
           termeni_curenti.append(lst[i])
       else:
           if lungime_curenta > lungime_maxima:
               lungime_maxima = lungime_curenta
               termeni_maximi = termeni_curenti
           lungime_curenta = 1
           termeni_curenti = [lst[i]]
   if lungime_curenta > lungime_maxima:
       lungime_maxima = lungime_curenta
       termeni_maximi = termeni_curenti
   return lungime_maxima, termeni_maximi

def afiseaza_secventa_uniforma(lungime: int, termeni: list[int]) -> None:

   """
   Afișează secvența uniformă găsită în fișierul de ieșire.
   """
   with open("secventauniforma.out", "w", encoding="utf-8") as f:
       if valideaza_intrare(lst):
           f.write("Datele sunt introduse corect.\n")
           f.write(str(lungime) + "\n")
           f.write(" ".join(map(str, termeni)))
       else:
           f.write("Datele nu corespund restricțiilor impuse.")

if __name__ == '__main__':

  # Citirea datelor de intrare din fișier
  with open("secventauniforma.in", "r") as f:
      # Citim lista de numere din prima linie a fișierului și o convertim la listă de int
      lst = list(map(int, f.readline().split()))

  # Găsirea secvenței uniforme și afișarea ei în fișierul de ieșire
  lungime, termeni = gaseste_secventa_uniforma(lst)
  afiseaza_secventa_uniforma(lungime, termeni)

</syntaxhighlight>

Explicatie

Funcția valideaza_intrare(lst: list[int]) -> bool verifică dacă datele de intrare sunt valide, adică:

lista are o lungime între 2 și 10^6; fiecare element al listei este un număr întreg între 0 și 10^9; toți termenii din listă sunt egali. Funcția returnează True dacă datele sunt valide și False în caz contrar.

Funcția gaseste_secventa_uniforma(lst: list[int]) -> tuple[int, list[int]] primește o listă de numere și încearcă să găsească cea mai lungă secvență uniformă din acea listă. Dacă datele de intrare nu sunt valide (conform funcției valideaza_intrare), se va returna o secvență nulă, adică o secvență cu o lungime de 0 și o listă goală de termeni.

Dacă datele de intrare sunt valide, funcția parcurge lista și verifică dacă fiecare element este egal cu elementul anterior. Dacă da, înseamnă că am găsit un termen nou în secvență uniformă curentă, iar lungimea acesteia crește cu 1 și adăugăm termenul la lista de termeni curenti. Dacă nu, înseamnă că am găsit o secvență uniformă mai mică decât cea curentă, deci verificăm dacă lungimea ei este mai mare decât lungimea maximă găsită până acum. Dacă da, actualizăm lungimea maximă și lista de termeni maximi.

După ce am parcurs toată lista, returnăm lungimea maximă și lista de termeni maximi.

Funcția afiseaza_secventa_uniforma(lungime: int, termeni: list[int]) -> None primește lungimea și lista de termeni a celei mai lungi secvențe uniforme găsite și le afișează într-un fișier de ieșire numit "secventauniforma.out". Dacă datele de intrare nu sunt valide, afișează un mesaj corespunzător în locul secvenței uniforme.

Observați că, în cadrul acestei funcții, se mai face încă o dată validarea datelor de intrare, folosind funcția valideaza_intrare(lst: list[int]) -> bool. Aceasta este o măsură de siguranță suplimentară, pentru a evita afișarea unei secvențe uniforme în cazul în care datele de intrare sunt invalide.

În blocul if __name__ == '__main__': citim datele de intrare din fișierul "secventauniform