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: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numerele p şi u, reprezentând indicii de început şi sfârşit ai secvenţei determinate, 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;
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 1

Intrare: secvpal.in; 12; 1 2 10 9 8 5 8 9 10 5 5 10
Ieșire: secvpal.out; Datele sunt introduse correct.; 3 9

Exemplu 2

Intrare: secvpal.in; 99; 9 2 8 4 7 1 23 37 7 3
Ieșire: secvpal.out; Datele nu corespund restricțiilor impuse.

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("Datele sunt introduse corect.")
       print(start, end)
   else:
       print("Datele nu corespund restrictiilor impuse.")

</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.