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 ⩽ n ⩽ 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 construieste_sir_simetric(n, caroiaj):

   sir = ""

   for k in range(n // 2 + 1):
       for i in range(k, n - k):
           sir += caroiaj[k][i]  # sus
       for i in range(k + 1, n - k):
           sir += caroiaj[i][n - k - 1]  # dreapta
       for i in range(n - k - 2, k - 1, -1):
           sir += caroiaj[n - k - 1][i]  # jos
       for i in range(n - k - 2, k, -1):
           sir += caroiaj[i][k]  # stanga

   return sir

def cea_mai_lunga_secventa_simetrica(sir):

   max_len = 0
   start = 0

   for i in range(1, len(sir)):
       odd_len = 1
       while i - odd_len >= 0 and i + odd_len < len(sir) and sir[i - odd_len] == sir[i + odd_len]:
           odd_len += 1

       even_len = 0
       while i - even_len - 1 >= 0 and i + even_len < len(sir) and sir[i - even_len - 1] == sir[i + even_len]:
           even_len += 1

       current_len = max(2 * odd_len - 1, 2 * even_len)
       if current_len > max_len:
           max_len = current_len
           start = i - current_len // 2

   return sir[start:start + max_len]

def main():

   # Citirea datelor de intrare
   with open("caroiaj.txt", "r") as file:
       n = int(file.readline().strip())
       caroiaj = [list(file.readline().strip()) for _ in range(n)]

   # Construirea șirului și găsirea celei mai lungi secvențe simetrice
   sir = construieste_sir_simetric(n, caroiaj)
   rezultat = cea_mai_lunga_secventa_simetrica(sir)

   # Scrierea rezultatului în fișierul de ieșire
   with open("caroiaj.txt", "w") as file_out:
       file_out.write(rezultat)

if __name__ == "__main__":

   main()

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