Editing 3374 - Caroiaj

== Enunt ==

Se consideră un caroiaj format din '''n''' linii și '''n''' coloane, fiecare element din caroiaj fiind o literă mică din alfabetul englez. Să se constuiască șirul de caractere obținut prin parcurgerea caroiajului pe chenare dinspre exteriorul spre interiorul caroiajului, fiecare chenar fiind parcurs în sensul arcelor de ceas, pornind din colțul stânga sus al fiecărui chenar. Determinați cea mai lungă secvență de caractere situate pe poziții alăturate în șirul construit, care este simetrică. Dacă există mai multe astfel de secvențe de lungime maximă, se va determina ultima dintre ele.

== Cerinta ==

Cunoscând numărul natural '''n''' și un caroiaj format din '''n''' linii și '''n''' coloane de litere mici ale alfabetului englez, să se determine cea mai lungă secvență de caractere situate pe poziții alăturate în șirul construit, care este simetrică. Dacă există mai multe secvențe simetrice de lungime maximă, se va determina ultima dintre ele.

== Date de intrare ==

Fișierul de intrare '''caroiajin.txt''' conţine pe prima linie, numărul natural ''''''n,iar pe următoarele '''n''' linii se află câte '''n''' caractere, litere mici ale alfabetului englez.

== Date de iesire ==

Pe prima linie a fişierului '''caroiajout.txt''' va fi scrisă ultima secvență simetrică de caractere, de lungime maximă din șirul format prin parcurgerea caroiajului de caractere pe chenare, dinspre exteriorul spre interiorul caroiajului, fiecare chenar fiind parcurs în sensul arcelor de ceas, pornind de la colțul din stânga sus al fiecărui chenar.

== Restrictii si precizari ==

*1 &les; n &les; 500
*literele mici din caroiaj aparțin alfabetului englez

== Exemplul 1 ==
;caroiajin.txt
:5
:abcde
:bceaf
:abade
:abbad
:ffabc 
;caroiajout.txt
:Datele introduse corespund restrictiilor impuse
:abcdefedcba

== Exemplul 2 ==
;caroiajin.txt
:4
:ABCDEF
:BceaF
:ABBad
:FFabC

:Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def parcurgere_caroiaj(n, caroiaj):
    rezultat = ""
    
    for i in range((n + 1) // 2):
        # Parcurgere pe chenarul exterior al caroiajului
        for j in range(i, n - i):
            rezultat += caroiaj[i][j]
        
        # Parcurgere pe chenarul din dreapta
        for j in range(i + 1, n - i):
            rezultat += caroiaj[j][n - i - 1]
        
        # Parcurgere pe chenarul din jos
        for j in range(n - i - 2, i - 1, -1):
            rezultat += caroiaj[n - i - 1][j]
        
        # Parcurgere pe chenarul din stanga
        for j in range(n - i - 2, i, -1):
            rezultat += caroiaj[j][i]

    return rezultat


def cea_mai_lunga_secventa_simetrica(șir):
    max_len = 0
    start = 0

    for i in range(1, len(șir)):
        # Căutăm palindrom la fiecare caracter
        j = 0
        while i - j >= 0 and i + j < len(șir) and șir[i - j] == șir[i + j]:
            j += 1

        current_len = 2 * j - 1
        if current_len > max_len:
            max_len = current_len
            start = i - j + 1

    return șir[start:start + max_len]


def verifica_rezultat(input_file, output_file):
    with open(input_file, "r") as f:
        n = int(f.readline())
        caroiaj = [list(f.readline().strip()) for _ in range(n)]

    with open(output_file, "r") as g:
        rezultat_asteptat = g.readline().strip()

    sir_construit = parcurgere_caroiaj(n, caroiaj)
    rezultat_program = cea_mai_lunga_secventa_simetrica(sir_construit)

    if rezultat_program == rezultat_asteptat:
        print("Rezultat corect!")
    else:
        print("Rezultat incorect!")
        print("Rezultat așteptat:")
        print(rezultat_asteptat)
        print("Rezultat obținut:")
        print(rezultat_program)

# Citire date de intrare
with open("caroiajin.txt", "r") as f:
    n = int(f.readline())
    caroiaj = [list(f.readline().strip()) for _ in range(n)]

# Construire șir parcurgând caroiajul
sir_construit = parcurgere_caroiaj(n, caroiaj)

# Determinare cea mai lungă secvență simetrică
rezultat = cea_mai_lunga_secventa_simetrica(sir_construit)

# Scriere rezultat în fișierul de ieșire
with open("caroiajout.txt", "w") as g:
    g.write(rezultat)

# Verificare rezultat pentru exemplul dat
verifica_rezultat("caroiajin.txt", "caroiajout.txt")

</syntaxhighlight>

== Explicatie ==

Șirul de caractere format la parcurgerea caroiajului pe chenare în maniera indicată în text, este: abcdefedcbaffaabceadabbba. Ultima secvență simetrică de lungime maximă este abcdefedcba.