0524 - SecvEgale1

Cerinţa

Se dă un vector cu n elemente, numere naturale. Determinați cea mai lungă secvență de elemente din vector care începe și se termină cu aceeași valoare. Dacă în vector există mai multe secvențe corecte de lungime maximă se va determina cea mai din stânga.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând elementele vectorului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou va afișa pe ecran indicii st dr ai capetelor secvenței determinate, separați printr-un spațiu, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ≤ n ≤ 1000
cele n numere citite vor fi mai mici decât 1.000.000.000
indexarea elementelor vectorului începe de la 1.

Exemplu 1

Intrare: 12; 6 6 8 3 6 6 3 8 4 3 3 4
Ieșire: Datele sunt introduse corect..; 4 11

Exemplu 2

Intrare: 11; 6 2 8 3 3 6 3 8 4 1 3 4
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

0524 - SecvEgale1

def validate_input(n, v):

   if not (isinstance(n, int) and n >= 1 and n <= 1000):
       return False
   if not all(isinstance(x, int) and x >= 0 and x < 1000000000 for x in v):
       return False
   return True

def find_identical_sequence(n, v):

   max_len = 0
   seq_start = None
   seq_end = None

   for i in range(n):
       for j in range(i+1, n+1):
           if v[i:j] == v[i:j][::-1] and j-i > max_len:
               seq_start = i+1
               seq_end = j
               max_len = j-i

   if max_len > 0:
       return (seq_start, seq_end)
   else:
       return None

if __name__ == "__main__":

   n = int(input())
   v = list(map(int, input().split()))

   if validate_input(n, v):
       result = find_identical_sequence(n, v)
       if result:
           print("Datele sunt introduse corect.")
           print(result[0], result[1])
       else:
           print("Nu exista secventa identica.")
   else:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie Rezolvare

Funcția validate_input primește n și v și verifică dacă n se află în intervalul [1, 1000] și dacă fiecare element al listei v se află în intervalul [0, 1000000000]. Dacă datele sunt valide, funcția returnează True, altfel returnează False.

Funcția find_identical_sequence primește n și v și parcurge fiecare posibilă subsecvență a lui v. Dacă subsecvența este identică cu inversul ei și este mai mare decât lungimea maximă găsită până acum, actualizează lungimea maximă și poziția de început și sfârșit a secvenței. Dacă nu se găsește o secvență identică, funcția returnează None.

În funcția if __name__ == "__main__", citim n și v și verificăm dacă datele sunt valide. Dacă sunt, apelăm find_identical_sequence și afișăm secvența identică dacă există. Altfel, afișăm un mesaj de eroare corespunzător.