0310 - SecvPal - Revision history

Monica Dragos at 22:24, 14 May 2023

2023-05-14T22:24:48Z

← Older revision		Revision as of 22:24, 14 May 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/310/secvpal 0310 - SecvPal]		Sursa: [https://www.pbinfo.ro/probleme/310/secvpal 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 ==		== 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ă.		Se dă un vector cu n elemente, numere naturale. Determinaţi secvenţa palindromică de lungime maximă.

Monica Dragos: /* Date de ieșire */

2023-05-14T22:24:00Z

Date de ieșire

← Older revision		Revision as of 22:24, 14 May 2023
Line 15:		Line 15:

	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', ~~iş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."'''.		'''"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 ==		== Restricţii şi precizări ==

Monica Dragos: /* Date de ieșire */

2023-05-14T22:23:48Z

Date de ieșire

← Older revision		Revision as of 22:23, 14 May 2023
Line 13:		Line 13:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fişierul de ieşire secvpal.out va conţine:~~
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', ~~apoi pe un rând nou~~ ''' 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."'''.		'''"Datele sunt introduse corect."''', iş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 ==		== Restricţii şi precizări ==

Flaviu at 21:21, 14 May 2023

2023-05-14T21:21:56Z

← Older revision		Revision as of 21:21, 14 May 2023
Line 27:		Line 27:
	: 1 2 10 9 8 5 8 9 10 5 5 10		: 1 2 10 9 8 5 8 9 10 5 5 10
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: secvpal.out		: secvpal.out
	~~: Datele sunt introduse correct.~~
	: 3 9		: 3 9

Line 37:		Line 37:
	: 9 2 8 4 7 1 23 37 7 3		: 9 2 8 4 7 1 23 37 7 3
	; Ieșire		; Ieșire
	~~: secvpal.out~~
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.

Line 46:		Line 45:
	# 0310 - SecvPal		# 0310 - SecvPal

	def ~~citire~~():		def validate_input(n, arr):
	n = ~~int(input()~~)		if not (1 <= n <= 1000):
	v = []		return False
	~~for i in range~~(n):		if len(arr) != n:
	~~v.extend~~(~~list(map(int~~, ~~input().split()))~~)		return False
	return v		return True

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

	~~def secv_palindrom(v):~~		max_length = 0
	~~n = len(v)~~
	~~max_len~~ = 0
	start = 0		start = 0
	end = 0		end = 0

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

	~~def validare(v, start, end):~~		return f"{start + 1} {end + 1}"
	return v[start~~:end~~+1~~] == v[start:~~end+1~~][::-1]~~

	if __name__ == "__main__":		if __name__ == "__main__":
	v = ~~citire()~~		file_name = "secvpal.in"
	(~~start~~, ~~end~~) = ~~secv_palindrom~~(v)		with open(file_name, "r") as file:
	~~if validare~~(v, ~~start, end~~):		n = int(file.readline())
	~~print~~(~~"Datele sunt introduse corect."~~)		arr = list(map(int, file.readline().split()))
	~~print~~(~~start~~, ~~end~~)
	~~else:~~		result = find_max_palindrome(n, arr)
	print(~~"Datele nu corespund restrictiilor impuse."~~)		print(result)


	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== 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 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).
	~~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~~.		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):

	~~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ă~~.		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.

	~~Î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.~~		Aceste funcții rezolvă problema cerută de determinare a celei mai lungi secvențe palindromice dintr-un vector

Flaviu at 07:57, 3 May 2023

2023-05-03T07:57:07Z

← Older revision		Revision as of 07:57, 3 May 2023
Line 15:		Line 15:
	Fişierul de ieşire secvpal.out va conţine:		Fişierul de ieşire secvpal.out va conţine:
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi pe un rând nou '''~~numărul c~~''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' 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 ==		== Restricţii şi precizări ==
Line 21:		Line 21:
	* numerele de pe a doua linie a fişierului de intrare vor avea cel mult 4 cifre;		* 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;		* dacă există mai multe secvenţe palindromice de lungime maximă, se va determina cea mai din stânga;
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: secvpal.in
	: 12		: 12
	: 1 2 10 9 8 5 8 9 10 5 5 10		: 1 2 10 9 8 5 8 9 10 5 5 10
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: secvpal.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 3 9		: 3 9

			== Exemplu 2 ==
			; Intrare
			: secvpal.in
			: 99
			: 9 2 8 4 7 1 23 37 7 3
			; Ieșire
			: secvpal.out
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:38, 28 April 2023

2023-04-28T14:38:09Z

← Older revision		Revision as of 14:38, 28 April 2023
Line 13:		Line 13:

	== Date de ieșire ==		== 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~~.		Fişierul de ieşire secvpal.out va conţine:
			Dacă datele sunt introduse corect, pe ecran se va afișa:
			'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
Line 24:		Line 26:
	: 1 2 10 9 8 5 8 9 10 5 5 10		: 1 2 10 9 8 5 8 9 10 5 5 10
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 3 9		: 3 9

Line 58:		Line 62:
	(start, end) = secv_palindrom(v)		(start, end) = secv_palindrom(v)
	if validare(v, start, end):		if validare(v, start, end):
			print("Datele sunt introduse corect.")
	print(start, end)		print(start, end)
	else:		else:
	print("~~Eroare: Secventa gasita~~ nu ~~este palindromica~~.")		print("Datele nu corespund restrictiilor impuse.")


	</syntaxhighlight>		</syntaxhighlight>

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/310/secvpal 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...

2023-04-17T20:54:27Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/310/secvpal 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...

New page

Sursa: [https://www.pbinfo.ro/probleme/310/secvpal 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 ===
<syntaxhighlight lang="python" line>
# 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.")

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