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

Datele nu corespund restricțiilor impuse.

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

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>