0310 - SecvPal

Sursa: 0310 - SecvPal

---

Cerinţa

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

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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", fişierul de ieşire secvpal.out 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

Datele sunt introduse correct.

secvpal.out

3 9

Exemplu 2

Intrare

secvpal.in

99

9 2 8 4 7 1 23 37 7 3

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 0310 - SecvPal

def validate_input(n, arr):
    if not (1 <= n <= 1000):
        return False
    if len(arr) != n:
        return False
    return True

def find_max_palindrome(n, arr):
    if not validate_input(n, arr):
        return "Datele nu corespund restricțiilor impuse."

    max_length = 0
    start = 0
    end = 0

    for i in range(n):
        for j in range(i, n):
            if arr[i:j+1] == arr[i:j+1][::-1] and len(arr[i:j+1]) > max_length:
                max_length = len(arr[i:j+1])
                start = i
                end = j

    return f"{start + 1} {end + 1}"


if __name__ == "__main__":
    file_name = "secvpal.in"
    with open(file_name, "r") as file:
        n = int(file.readline())
        arr = list(map(int, file.readline().split()))

    result = find_max_palindrome(n, arr)
    print(result)

Explicatie Rezolvare

Funcția validate_input(n, arr): Această funcție primește doi parametri, n și arr, reprezentând numărul de elemente din vector (n) și vectorul în sine (arr). Verifică dacă numărul n se află în intervalul valid, adică între 1 și 1000. Dacă nu este adevărată această condiție, returnează False, semnalând că datele nu corespund restricțiilor impuse. Verifică dacă lungimea vectorului arr este egală cu n. Dacă această condiție nu este îndeplinită, returnează False. Dacă toate verificările sunt trecute cu succes, înseamnă că datele de intrare sunt valide, astfel că returnează True. Funcția find_max_palindrome(n, arr):

Această funcție primește doi parametri, n și arr, reprezentând numărul de elemente din vector (n) și vectorul în sine (arr). Verifică mai întâi validitatea datelor de intrare folosind funcția validate_input(n, arr). Dacă datele nu sunt valide, returnează un mesaj corespunzător. Inițializează variabilele max_length, start și end cu valorile 0. Acestea vor fi actualizate pe măsură ce se găsesc secvențe palindromice de lungime maximă. Parcurge toate sub-secvențele posibile ale vectorului, utilizând două bucle for imbricate (i și j). Verifică dacă sub-secvența curentă, arr[i:j+1], este un palindrom. Aceasta se realizează prin compararea sub-secvenței cu reversul său, arr[i:j+1][::-1]. Dacă sub-secvența este un palindrom și are o lungime mai mare decât max_length, se actualizează max_length cu noua valoare a lungimii, iar start și end cu indicii de început și sfârșit ai secvenței palindromice. După parcurgerea tuturor sub-secvențelor, se returnează o frază formatată care indică indicii de început și sfârșit ai celei mai lungi secvențe palindromice găsite în vectorul dat. În funcția if __name__ == "__main__", se realizează citirea datelor de intrare din fișierul "secvpal.in" și se apelează funcția find_max_palindrome cu valorile citite. Rezultatul este apoi afișat pe ecran.

Aceste funcții rezolvă problema cerută de determinare a celei mai lungi secvențe palindromice dintr-un vector