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 2

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.")

1. 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()))

1. 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>