2806 - Secventa Para

Cerinţa

Numim secvență pară într-un șir o succesiune de termeni ai șirului cu proprietatea că sunt numere pare și că se află pe poziții consecutive în șir; orice secvență are cel puțin doi termeni și este maximală în raport cu proprietatea precizată (dacă i se adaugă un alt termen, secvența își pierde această proprietate). Lungimea secvenței este egală cu numărul termenilor săi.

Scrieți un program care citește un șir de cel mult 10^6 numere naturale din intervalul [0,10^9] și determină numărul de secvențe pare de lungime maximă din șir. Se cere să se afișeze poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.

Date de intrare

Fișierul de intrare secventapara.in conține cel mult 10^6 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 secventapara.out va conține pe prima linie numărul de secvențe pare de lungime maximă din șir. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

Proiectați un algoritm eficient din punctul de vedere al spațiului de memorie utilizat şi al timpului de executare:
se recomandă o soluție care să nu memoreze elementele șirului într-un tablou sau altă structură de date similară.

Exemple

Exemplul 1

secventapara.in: 1 2 3 4 6 10 2 8 5 7 9 4 6 10 121 20 4 11 10 2 5 2 6 8 10 16
Ecran: Datele sunt introduse corect.
secventapara.out: 2

Exemplul 2

secventapara.in:

1 3 5 7 9
Ecran: Datele sunt introduse corect.
secventapara.out: 0

Exemplul 3

secventapara.in: 2 -4 6 8 10
Ecran: Datele nu corespund restricțiilor impuse.
secventapara.out: 1

Rezolvare

2806 - Secventa Para

def validare_date(sir):

   if len(sir) > 10**6 or any(num < 0 or num > 10**9 for num in sir):
       print("Datele nu corespund restricțiilor impuse.")
       return False
   else:
       print("Datele sunt introduse corect.")
       return True

def numar_si_lungime_maxima_secvente_pare(sir):

   lungime_maxima = 0
   lungime_curenta = 0
   numar_secvente_maxime = 0

   for num in sir:
       if num % 2 == 0:
           lungime_curenta += 1
           if lungime_curenta > lungime_maxima:
               lungime_maxima = lungime_curenta
               numar_secvente_maxime = 1
           elif lungime_curenta == lungime_maxima:
               numar_secvente_maxime += 1
       else:
           lungime_curenta = 0

   return numar_secvente_maxime, lungime_maxima

if __name__ == '__main__':

   # Citire date din fisier
   with open("secventapara.in", "r") as f:
       sir = list(map(int, f.readline().split()))

   # Verificare validitate date de intrare
   if validare_date(sir):
       # Calcul numar si lungime maxima secvente pare
       numar_secvente_maxime, lungime_maxima = numar_si_lungime_maxima_secvente_pare(sir)
       # Afisare numar si lungime maxima secvente pare
       with open("secventapara.out", "w") as g:
           g.write(str(numar_secvente_maxime) + '\n')
           # g.write(str(lungime_maxima))

</syntaxhighlight>

Explicatie

Funcția validare_date(sir) verifică dacă datele de intrare sunt valide, adică:

lista are o lungime mai mică sau egală cu 10^6; toți termenii din listă sunt numere întregi între 0 și 10^9. Funcția returnează True dacă datele sunt valide și False în caz contrar. În plus, funcția afișează un mesaj corespunzător pentru a confirma validitatea datelor.

Funcția numar_si_lungime_maxima_secvente_pare(sir) primește o listă de numere și încearcă să găsească numărul și lungimea maximă a secvențelor pare din acea listă. Pentru a face acest lucru, funcția parcurge lista și numără lungimea fiecărei secvențe de numere pare. Dacă lungimea unei secvențe este mai mare decât lungimea maximă găsită până acum, atunci se actualizează lungimea maximă și se resetează numărul de secvențe maximale. Dacă lungimea unei secvențe este egală cu lungimea maximă găsită până acum, atunci se adaugă o secvență suplimentară la numărul de secvențe maximale.

Funcția returnează numărul de secvențe maximale și lungimea maximă a secvențelor pare.

În blocul if __name__ == '__main__': citim datele de intrare din fișierul "secventapara.in" și apoi verificăm dacă datele sunt valide folosind funcția validare_date(sir). Dacă datele nu sunt valide, se afișează un mesaj corespunzător și se oprește execuția programului.

Dacă datele sunt valide, se apelează funcția numar_si_lungime_maxima_secvente_pare(sir) pentru a găsi numărul și lungimea maximă a secvențelor pare și se afișează în fișierul de ieșire "secventapara.out".