0310 - SecvPal

Sursa: 0310 - SecvPal

O secvenţă a unui vector se numeşte palindromică dacă primul element ale secvenţei este egal cu ultimul, al doilea cu penultimul, etc.

Cerinţa

Se dă un vector cu n elemente, numere naturale. Determinaţi secvenţa palindromică de lungime maximă.

Date de intrare

Fişierul de intrare secvpal.in conţine pe prima linie numărul n; urmează cele n elemente ale vectorului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieșire

Fişierul de ieşire secvpal.out va conţine pe prima linie numerele p şi u, reprezentând indicii de început şi sfârşit ai secvenţei determinate.

Restricţii şi precizări

1 ≤ n ≤ 1000;
numerele de pe a doua linie a fişierului de intrare vor avea cel mult 4 cifre;
dacă există mai multe secvenţe palindromice de lungime maximă, se va determina cea mai din stânga;

Exemplu

Intrare: 12; 1 2 10 9 8 5 8 9 10 5 5 10
Ieșire: 3 9

Rezolvare

Rezolvare ver. 1

0310 - SecvPal

def citire():

   n = int(input())
   v = []
   for i in range(n):
       v.extend(list(map(int, input().split())))
   return v

def secv_palindrom(v):

   n = len(v)
   max_len = 0
   start = 0
   end = 0
   for i in range(n):
       for j in range(i, n):
           if v[i:j+1] == v[i:j+1][::-1] and j-i+1 > max_len:
               max_len = j-i+1
               start = i
               end = j
   return (start, end)

def validare(v, start, end):

   return v[start:end+1] == v[start:end+1][::-1]

if __name__ == "__main__":

   v = citire()
   (start, end) = secv_palindrom(v)
   if validare(v, start, end):
       print(start, end)
   else:
       print("Eroare: Secventa gasita nu este palindromica.")

</syntaxhighlight>

Explicatie Rezolvare

Funcția citire citește vectorul v din input, care conține numerele naturale date pe mai multe linii, separate prin spații.

Funcția secv_palindrom primește ca parametru vectorul v și găsește secvența palindromică de lungime maximă, returnând indicii de început și de sfârșit ai acestei secvențe. Această funcție utilizează o metodă brute-force de căutare a tuturor sub-șirurilor posibile din vector și verificarea lor dacă sunt palindromice.

Funcția validare primește vectorul v și indicii de început și de sfârșit ai secvenței palindromice găsite și verifică dacă această secvență este într-adevăr palindromică.

În funcția main, se apelează funcția citire pentru a citi vectorul v din input, apoi se apelează funcția secv_palindrom pentru a găsi secvența palindromică de lungime maximă și se verifică cu ajutorul funcției validare dacă aceasta este într-adevăr palindromică. Dacă este, se afișează indicii de început și de sfârșit ai secvenței găsite, altfel se afișează un mesaj de eroare.