2533 - SecventaIncadrata

Sursa: - SecventaIncadrata

---

Cerinţa

Numim secvență încadrată a unui șir de numere naturale un subșir al acestuia, format din termeni aflați pe poziții consecutive în șirul dat, subșir care începe și se termină cu aceeași valoare. Lungimea secvenței este egală cu numărul de termeni ai acesteia.

Să se determine secvențele încadrate dintr-un șir, care au lungimea maximă.

Date de intrare

Fișierul de intrare secventaincadrata.in conține cel puțin două și cel mult 106 numere naturale din intervalul [0,9], separate printr-un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi in fișierul de ieșire secventaincadrata.out va conține pe prima linie numărul L, reprezentând lungimea maximă a secvențelor încadrate, iar pe a doua linie a fișierului valoarea primului termen al fiecărei secvențe încadrate de lungime maximă, în ordine crescătoare și separate printr-un spațiu. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• în șir există ce puțin doi termeni egali
• proiectați un algoritm eficient din punctul de vedere al timpului de executare și a memoriei utilizate
• se recomandă o soluție care să evite stocarea tuturor valorilor citite într-un tablou sau într-o altă structură de date similară

Exemple

Exemplul 1

secventaincadrata.in

3 1 5 2 4 5 5 2 5 9 5 7 4 6 8 0 8

Ieșire

Datele sunt corecte.

secventaincadrata.out

9

4 5

Exemplul 2

secventaincadrata.in

9 0 1 3 4 7 1 8 9 1 3 1 2 3 4 6

Ieșire

Datele sunt corecte.

secventaincadrata.out

11

3 4

Exemplul 3

secventaincadrata.in

314441 41241241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 2533 secventaincadrata

def secventaincadrata(vector):

    with open("secventaincadrata.out","w") as f:
       A = [float('inf')] * 10
       lmax = [0] * 10
       L = 0
       i = 1

       for x in vector:
           lmax[x] = max(i - A[x] + 1, lmax[x])
           if A[x] == float('inf'):
               A[x] = i
           L = max(lmax[x], L)
           i += 1

       f.write(str(L) + '\n')
       for i in range(10):
           if lmax[i] == L:
               f.write(str(i) + ' ')
       f.write('\n')
   

def conform_restrictiilor():

   with open('secventaincadrata.in') as f:
       vector = list(map(int, f.read().split()))
   if len(vector) < 2 or len(vector) > 106:
       print("Datele nu sunt conform restricțiilor impuse.")
       exit()
   for x in vector:
       if x > 9:
           print("Datele nu sunt conform restricțiilor impuse.")
           exit()
   print("Datele sunt corecte.")
   return vector 

if __name__ == '__main__':

   vector= conform_restrictiilor()
   secventaincadrata(vector)

</syntaxhighlight>