2796 - Secvente Neuniforme

Cerinţa

Numim secvență neuniformă a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, cu proprietatea că oricare trei termeni aflați pe poziții consecutive sunt diferiți. Lungimea secvenței este egală cu numărul de termeni ai acesteia.

Se dă un șir de cel mult 10^6 numere naturale din intervalul [0,9], în care există cel puțin trei termeni diferiți pe poziții consecutive. Se cere să se afișeze lungimea maximă a unei secvențe neuniforme a șirului dat.

Date de intrare

Fișierul de intrare secventeneuniforme.in conține un șir de cel mult 10^6 numere naturale din intervalul [0,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 secventeneuniforme.out va conține pe prima linie lungimea maximă a unei secvențe neuniforme a șirului aflat în fișierul de intrare. Î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

7 7 1 3 7 7 5 3 3 3 7 8 9

Ecran

Datele sunt introduse corect.

secventapara.out

4

Exemplul 2

secventeneuniforme.in

2 2 2 2 2 2 2 2 2 2 2 2 2

Ecran

Datele nu corespund restricțiilor impuse.

secventeneuniforme.out

0

Exemplul 3

secventeneuniforme.in

1 1 1 2 3 3 3 3 3 3 2 2 2 1 1 1 2 2 2 2

Ecran

Datele sunt introduse corect.

secventeneuniforme.out

3

Rezolvare

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

1. 2796 - Secvente Neuniforme

def validare_date_intrare(sir):

   
   Verifică dacă datele din fișierul de intrare corespund cerințelor impuse.
   
   if len(sir) == 0:
       return False
   for i in range(len(sir) - 2):
       if sir[i] != sir[i + 1] and sir[i + 1] != sir[i + 2] and sir[i] != sir[i + 2]:
           return True
   return False

def rezolvare(sir):

   
   Găsește lungimea maximă a unei secvențe neuniforme în șirul dat.
   
   lungime_maxima = 0
   lungime_curenta = 0
   for i in range(len(sir) - 2):
       if sir[i] != sir[i + 1] and sir[i + 1] != sir[i + 2] and sir[i] != sir[i + 2]:
           lungime_curenta += 1
       else:
           if lungime_curenta > lungime_maxima:
               lungime_maxima = lungime_curenta
           lungime_curenta = 0
   if lungime_curenta > lungime_maxima:
       lungime_maxima = lungime_curenta
   return lungime_maxima + 2

if __name__ == '__main__':

   # Citim datele din fișierul de intrare
   with open('secventapara.in', 'r') as f:
       sir = list(map(int, f.readline().split()))

   # Validăm datele de intrare
   if not validare_date_intrare(sir):
       print("Datele nu corespund restricțiilor impuse.")
       exit()

   # Rezolvăm problema și afișăm rezultatul
   lungime_maxima = rezolvare(sir)
   # Scriem rezultatul în fișierul de ieșire
   with open('secventeneuniforme.out', 'w') as f:
       print("Datele sunt introduse corect.")
       f.write(str(lungime_maxima))

</syntaxhighlight>

Explicatie

Funcția validare_date_intrare(sir) verifică dacă datele din fișierul de intrare corespund cerințelor impuse, adică există cel puțin o secvență de cel puțin trei numere consecutive în care niciunul dintre ele nu este egal cu niciunul dintre celelalte două. Dacă există cel puțin o astfel de secvență, funcția returnează True, altfel returnează False.

Funcția rezolvare(sir) primește un șir de numere și încearcă să găsească lungimea maximă a unei secvențe neuniforme din acesta. Pentru a face acest lucru, funcția parcurge lista și numără lungimea fiecărei secvențe de cel puțin trei numere consecutive în care niciunul dintre ele nu este egal cu niciunul dintre celelalte două. Dacă lungimea unei astfel de secvențe este mai mare decât lungimea maximă găsită până acum, atunci se actualizează lungimea maximă.

Î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_intrare(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 rezolvare(sir) pentru a găsi lungimea maximă a unei secvențe neuniforme și se afișează în consolă mesajul "Datele sunt introduse corect.". În plus, se scrie lungimea maximă a secvenței neuniforme găsite în fișierul de ieșire "secventeneuniforme.out".