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

secventapara.out

2

Exemplul 2

secventapara.in:

1 3 5 7 9

secventapara.out

0

Exemplul 3

secventapara.in

2 4 6 8 10

secventapara.out

1

Rezolvare

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

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

1. Citire date din fisier

with open("secventapara.in", "r") as f:

   sir = list(map(int, f.readline().split()))

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