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.")

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.