3374 - Caroiaj - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T12:06:31Z

Rezolvare

@@ Line 85: / Line 85: @@
      return șir[start:start + max_len]
 # Citire date de intrare
@@ Line 100: / Line 120: @@
 with open("caroiajout.txt", "w") as g:
      g.write(rezultat)
 </syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T11:07:03Z

Rezolvare

← Older revision		Revision as of 11:07, 27 December 2023
Line 45:		Line 45:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~construieste_sir_simetric~~(n, caroiaj):		def parcurgere_caroiaj(n, caroiaj):
	~~sir~~ = ""		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]

	~~for k in range(n // 2 + 1):~~		return rezultat
	~~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~~):		def cea_mai_lunga_secventa_simetrica(șir):
	max_len = 0		max_len = 0
	start = 0		start = 0

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

	~~even_len = 0~~		current_len = 2 * j - 1
	~~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:		if current_len > max_len:
	max_len = current_len		max_len = current_len
	start = i - ~~current_len // 2~~		start = i - j + 1

			return șir[start:start + max_len]

	~~return sir[start:start + max_len]~~

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

	# ~~Construirea șirului și găsirea celei mai lungi secvențe simetrice~~		# Construire șir parcurgând caroiajul
	~~sir~~ = ~~construieste_sir_simetric~~(n, caroiaj)		sir_construit = parcurgere_caroiaj(n, caroiaj)
	~~rezultat = cea_mai_lunga_secventa_simetrica(sir~~)

	# ~~Scrierea rezultatului în fișierul de ieșire~~		# Determinare cea mai lungă secvență simetrică
	~~with open("caroiaj.txt", "w") as file_out:~~		rezultat = cea_mai_lunga_secventa_simetrica(sir_construit)
	~~file_out.write~~(~~rezultat~~)

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

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 11:05, 27 December 2023

2023-12-27T11:05:46Z

← Older revision		Revision as of 11:05, 27 December 2023
Line 1:		Line 1:
	== Enunt ==		== 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.		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 ==		== 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.		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 ==		== Date de intrare ==

	Fișierul de intrare ~~caroiaj~~.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.		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 ==		== Date de iesire ==

	Pe prima linie a fişierului ~~caroiaj~~.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.		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 ==		== Restrictii si precizari ==

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

	== Exemplul 1 ==		== Exemplul 1 ==
	;~~Intrare~~		;caroiajin.txt
	:5		:5
	:abcde		:abcde
Line 28:		Line 28:
	:abbad		:abbad
	:ffabc		:ffabc
	;~~Iesire~~		;caroiajout.txt
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:abcdefedcba		:abcdefedcba

	== Exemplul 2 ==		== Exemplul 2 ==
	;~~Intrare~~		;caroiajin.txt
	:4		:4
	:ABCDEF		:ABCDEF
Line 39:		Line 39:
	:ABBad		:ABBad
	:FFabC		:FFabC
	~~;Iesire~~
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa: Pagină nouă: == 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 ș...

2023-12-16T09:59:34Z

Pagină nouă: == 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 ș...

New page

== 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 caroiaj.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 caroiaj.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 ==
;Intrare
:5
:abcde
:bceaf
:abade
:abbad
:ffabc
;Iesire
;Datele introduse corespund restrictiilor impuse
:abcdefedcba

== Exemplul 2 ==
;Intrare
:4
:ABCDEF
:BceaF
:ABBad
:FFabC
;Iesire
;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.