0181 - SecvCresc - Revision history

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

2023-05-14T20:36:25Z

Date de ieșire

← Older revision		Revision as of 20:36, 14 May 2023
Line 9:		Line 9:

	== Date de ieșire ==		== Date de ieșire ==
	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 fișierul de ieșire secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de 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 fișierul de ieșire secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de 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."'''.

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

2023-05-14T20:00:44Z

Date de ieșire

← Older revision		Revision as of 20:00, 14 May 2023
Line 9:		Line 9:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire secvcresc.out:~~ 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 '''~~secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de 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 fișierul de ieșire secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de 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:53, 13 May 2023

2023-05-13T21:53:14Z

← Older revision		Revision as of 21:53, 13 May 2023
Line 22:		Line 22:
	: 2 6 4 5 8 9 6 3 4		: 2 6 4 5 8 9 6 3 4
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: secvcresc.out		: secvcresc.out
	~~: Datele sunt introduse correct.~~
	: 3 6		: 3 6

	== Exemplu 2 ==		== Exemplu 2 ==
	; Intrare		; Intrare
	: secvcresc.in		: secvcresc.in
	: 9		: 5
	: ~~2 6 4 5 8 9 6 3 4~~		: 1000 200 300 400 500
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: secvcresc.out		: secvcresc.out
	: ~~Datele~~ nu ~~corespund restricțiilor impuse.~~		: Iar sevcresc.out nu va fi generat deoarece datele nu sunt crescatoare
	~~: 2 4 5~~
	== Rezolvare ==		== Rezolvare ==
	=== Rezolvare ver. 1 ===		=== Rezolvare ver. 1 ===
Line 39:		Line 40:
	# 0181 - SecvCresc		# 0181 - SecvCresc

	def ~~citire_date~~():		def lungime_secventa_crescatoare(n, v):
	n ~~= int(input())~~		"""Funcția primește un număr n reprezentând numărul de elemente din vectorul v și un vector v de n elemente.
	v ~~= []~~		Returnează indicii secvenței maxime ordonate crescător din vectorul v."""
	~~for i in range(~~n):		st = dr = 0
	v.~~extend(map(int, input().split()))~~		max_len = 0
	~~return n,~~ v		len_curenta = 1

	~~def secv_cresc(n, v):~~
	~~st_max~~ = ~~dr_max~~ = 0
	~~l_max~~ = 1
	~~l_crt~~ = 1
	for i in range(1, n):		for i in range(1, n):
	if v[i] > v[i-1]:		if v[i] > v[i-1]:
	~~l_crt~~ += 1		len_curenta += 1
	else:		else:
	if ~~l_crt~~ > ~~l_max~~:		if len_curenta > max_len:
	~~l_max~~ = ~~l_crt~~		max_len = len_curenta
	~~st_max~~ = i - ~~l_max~~		st = i - max_len
	~~dr_max~~ = i - 1		dr = i - 1
	~~l_crt~~ = 1		len_curenta = 1
	if ~~l_crt~~ > ~~l_max~~:		if len_curenta > max_len:
	~~l_max~~ = ~~l_crt~~		max_len = len_curenta
	~~st_max~~ = n - ~~l_max~~		st = n - max_len
	~~dr_max~~ = n - 1		dr = n - 1
	return ~~l_max, st_max~~ + 1, ~~dr_max~~ + 1		return st+1, dr+1

	~~def validare(n, v):~~
	~~if len(v) != n:~~
	~~return False~~
	~~for x in v:~~
	~~if x < 1 or x >= 1000000:~~
	~~return False~~
	~~return True~~

	if __name__ == '__main__':		if __name__ == '__main__':
	n~~, v~~ = ~~citire_date~~()		try:
	~~if validare~~(n~~, v~~):		with open('secvcresc.in', 'r') as f:
	~~print~~(~~"Datele sunt introduse corect~~.")		n = int(f.readline())
	~~l, st, dr = secv_cresc~~(~~n, v~~)		v = []
	print(l)		for _ in range(n):
			v += list(map(int, f.readline().split()))
			except FileNotFoundError:
			print('Datele nu corespund restricțiilor impuse.')
	else:		else:
	print("Datele nu corespund restricțiilor impuse.")		if n > 0 and n <= 10000 and all(elem < 1000000 for elem in v):
			st, dr = lungime_secventa_crescatoare(n, v)
			print('Datele sunt introduse corect.')
			with open('secvcresc.out', 'w') as f:
			f.write(str(st) + ' ' + str(dr) + '\n')
			else:
			print('Datele nu corespund restricțiilor impuse.')

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	Funcția ~~citire_date() citește valorile~~ din ~~fișier~~ și ~~le salvează într-~~un vector~~, iar secv_cresc() găsește cea mai lungă secvență crescătoare din acest vector~~ și returnează ~~lungimea acesteia și pozițiile de început și de sfârșit~~. ~~Funcția validare() verifică dacă datele~~ de intrare ~~sunt corecte (conform restricțiilor~~ din ~~enunț)~~.		Funcția lungime_secventa_crescatoare primește un număr n reprezentând numărul de elemente din vectorul v și un vector v de n elemente și returnează indicii secvenței maxime ordonate crescător din vectorul v.
			În funcția principală if __name__ == '__main__'::
	~~În cadrul funcției secv_cresc() se parcurge vectorul și se verifică dacă fiecare element este mai mare decât elementul precedent.~~ Dacă ~~acesta este cazul~~, ~~lungimea secvenței curente crește cu 1. Dacă~~ se ~~întâlnește un element care~~ nu ~~este mai mare decât precedentul, se verifică dacă lungimea secvenței curente este mai mare decât lungimea maximă până în acest moment și se actualizează variabilele corespunzătoare~~.		Se încearcă deschiderea fișierului de intrare 'secvcresc.in' și citirea datelor din el.
			Dacă fișierul nu poate fi deschis, se afișează mesajul "Datele nu corespund restricțiilor impuse."
	~~La final, se verifică dacă ultima secvență~~ de elemente este mai ~~lungă~~ decât ~~cea maximă găsită până acum~~ și se ~~actualizează variabilele corespunzătoare.~~		Dacă datele sunt corect introduse (numărul de elemente n este între 1 și 10000 și toate elementele vectorului v sunt mai mici decât 1000000), se calculează indicii secvenței maxime ordonate crescător și se afișează mesajul "Datele sunt introduse corect.".
			Dacă datele nu corespund restricțiilor impuse, se afișează mesajul "Datele nu corespund restricțiilor impuse.".
	~~Programul~~ afișează "Datele sunt introduse corect." ~~și lungimea celei mai lungi secvențe crescătoare dacă~~ datele ~~de intrare sunt corecte. În caz contrar~~, se afișează "Datele nu corespund restricțiilor impuse.".		Indicii secvenței maxime ordonate crescător sunt scriși în fișierul de ieșire 'secvcresc.out'.

Flaviu at 07:31, 3 May 2023

2023-05-03T07:31:33Z

← Older revision		Revision as of 07:31, 3 May 2023
Line 10:		Line 10:
	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire secvcresc.out: Dacă datele sunt introduse corect, pe ecran se va afișa:		Fișierul de ieșire secvcresc.out: 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 '''secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de 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."'''.


Line 16:		Line 16:
	* 0 < n ≤ 10.000		* 0 < n ≤ 10.000
	* elementele vectorului vor fi mai mici decât 1.000.000 și sunt numerotate de la 1		* elementele vectorului vor fi mai mici decât 1.000.000 și sunt numerotate de la 1
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: secvcresc.in
	: 9		: 9
	: 2 6 4 5 8 9 6 3 4		: 2 6 4 5 8 9 6 3 4
	; Ieșire		; Ieșire
			: secvcresc.out
			: Datele sunt introduse correct.
			: 3 6
			== Exemplu 2 ==
			; Intrare
			: secvcresc.in
			: 9
			: 2 6 4 5 8 9 6 3 4
			; Ieșire
			: secvcresc.out
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	: ~~3 6~~		: 2 4 5

	== Rezolvare ==		== Rezolvare ==
	=== Rezolvare ver. 1 ===		=== Rezolvare ver. 1 ===

Flaviu at 18:29, 27 April 2023

2023-04-27T18:29:28Z

← Older revision		Revision as of 18:29, 27 April 2023
Line 9:		Line 9:

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire secvcresc.out va ~~conține~~ pe ~~prima linie numerele st și dr~~, reprezentând ~~indicii de început și de sfârșit ai secvenței determinate~~.		Fișierul de ieșire secvcresc.out: 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 19:		Line 21:
	: 2 6 4 5 8 9 6 3 4		: 2 6 4 5 8 9 6 3 4
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: 3 6		: 3 6

Line 26:		Line 29:
	# 0181 - SecvCresc		# 0181 - SecvCresc

	def ~~citire~~():		def citire_date():
	~~with open("secvcresc.in", "r") as f:~~		n = int(input())
	n = int(~~f.readline~~())		v = []
	v = []		for i in range(n):
	for ~~line~~ in f:		v.extend(map(int, input().split()))
	v ~~+= list~~(map(int, ~~line~~.split()))
	return n, v		return n, v

	def ~~rezolvare~~(n, v):		def secv_cresc(n, v):
	~~max_length~~ = 1		st_max = dr_max = 0
	~~max_start~~ = ~~max_end = start = end = 0~~		l_max = 1
	~~length~~ = 1		l_crt = 1
	for i in range(1, n):		for i in range(1, n):
	if v[i] > v[i - 1]:		if v[i] > v[i-1]:
	~~length~~ += 1		l_crt += 1
	~~end = i~~
	else:		else:
	if ~~length~~ > ~~max_length~~:		if l_crt > l_max:
	~~max_length~~ = ~~length~~		l_max = l_crt
	~~max_start, max_end~~ = ~~start, end~~		st_max = i - l_max
	~~length~~ = 1		dr_max = i - 1
	~~start~~ = ~~end = i~~		l_crt = 1
	if ~~length~~ > ~~max_length~~:		if l_crt > l_max:
	~~max_length~~ = ~~length~~		l_max = l_crt
	~~max_start, max_end~~ = ~~start, end~~		st_max = n - l_max
	return ~~max_start~~ + 1, ~~max_end~~ + 1		dr_max = n - 1
			return l_max, st_max + 1, dr_max + 1

	def validare(n, v~~, start, end~~):		def validare(n, v):
	for i in ~~range(start - 1, end - 1)~~:		if len(v) != n:
	if ~~v[i]~~ >= ~~v[i + 1]~~:		return False
			for x in v:
			if x < 1 or x >= 1000000:
	return False		return False
	return True		return True

	if __name__ == "__main__":		if __name__ == '__main__':
	n, v = ~~citire~~()		n, v = citire_date()
	~~start, end = rezolvare~~(n, v)		if validare(n, v):
	~~with open~~("~~secvcresc~~.~~out", "w~~") ~~as f:~~		print("Datele sunt introduse corect.")
	~~f.write(f"{start} {end}\n")~~		l, st, dr = secv_cresc(n, v)
	~~if validare~~(n, v~~, start, end~~):		print(l)
	print(~~"Rezultat corect!"~~)
	else:		else:
	print("~~Rezultat incorect!~~")		print("Datele nu corespund restricțiilor impuse.")

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Pentru a rezolva această problemă~~, ~~putem parcurge vectorul~~ și ~~ține în variabila lungime~~ lungimea ~~secvenței curente. De asemenea, putem ține~~ și ~~variabilele start și end care reprezintă indicele~~ de început și sfârșit ~~al secvenței curente~~. ~~Dacă găsim o valoare~~ mai mare decât ~~precedenta~~, ~~atunci~~ lungimea secvenței crește ~~și actualizăm end~~ cu ~~indicele curent~~. Dacă ~~găsim o valoare~~ mai ~~mică sau egală cu precedenta~~, ~~atunci secvența curentă~~ se ~~termină~~ și ~~verificăm~~ dacă este mai lungă decât cea maximă găsită până acum. ~~Dacă da~~, ~~actualizăm variabilele max_start, max_end și max_length~~
			Funcția citire_date() citește valorile din fișier și le salvează într-un vector, iar secv_cresc() găsește cea mai lungă secvență crescătoare din acest vector și returnează lungimea acesteia și pozițiile de început și de sfârșit. Funcția validare() verifică dacă datele de intrare sunt corecte (conform restricțiilor din enunț).

			În cadrul funcției secv_cresc() se parcurge vectorul și se verifică dacă fiecare element este mai mare decât elementul precedent. Dacă acesta este cazul, lungimea secvenței curente crește cu 1. Dacă se întâlnește un element care nu este mai mare decât precedentul, se verifică dacă lungimea secvenței curente este mai mare decât lungimea maximă până în acest moment și se actualizează variabilele corespunzătoare.

			La final, se verifică dacă ultima secvență de elemente este mai lungă decât cea maximă găsită până acum și se actualizează variabilele corespunzătoare.

			Programul afișează "Datele sunt introduse corect." și lungimea celei mai lungi secvențe crescătoare dacă datele de intrare sunt corecte. În caz contrar, se afișează "Datele nu corespund restricțiilor impuse.".

Flaviu at 20:04, 17 April 2023

2023-04-17T20:04:13Z

← Older revision		Revision as of 20:04, 17 April 2023
Line 26:		Line 26:
	# 0181 - SecvCresc		# 0181 - SecvCresc

	with open("secvcresc.in") as ~~fin~~:		def citire():
	n = int(~~fin~~.readline())		with open("secvcresc.in", "r") as f:
	v = []		n = int(f.readline())
	for _ in ~~range(n)~~:		v = []
	v += list(map(int, ~~fin.readline()~~.split()))		for line in f:
			v += list(map(int, line.split()))
			return n, v

	max_start, max_end = 0, ~~0 # indicii de început și sfârșit ai secvenței maximale~~		def rezolvare(n, v):
	~~cur_start~~, ~~cur_end~~ = 0, ~~0 # indicii de început și sfârșit ai secvenței crescătoare curente~~		max_length = 1
	~~max_len~~ = 1 ~~# lungimea maximă a secvenței crescătoare~~		max_start = max_end = start = end = 0
	~~cur_len~~ = 1 ~~# lungimea secvenței crescătoare curente~~		length = 1
			for i in range(1, n):
			if v[i] > v[i - 1]:
			length += 1
			end = i
			else:
			if length > max_length:
			max_length = length
			max_start, max_end = start, end
			length = 1
			start = end = i
			if length > max_length:
			max_length = length
			max_start, max_end = start, end
			return max_start + 1, max_end + 1

	for i in range(1, n):		def validare(n, v, start, end):
	if v[i] > v[i - 1]:		for i in range(start - 1, end - 1):
	~~cur_len += 1~~		if v[i] >= v[i + 1]:
	~~cur_end = i~~		return False
	if ~~cur_len > max_len~~:		return True
	~~max_start~~ = ~~cur_start~~
	~~max_end~~ = ~~cur_end~~		if __name__ == "__main__":
	~~max_len = cur_len~~		n, v = citire()
			start, end = rezolvare(n, v)
			with open("secvcresc.out", "w") as f:
			f.write(f"{start} {end}\n")
			if validare(n, v, start, end):
			print("Rezultat corect!")
	else:		else:
	~~cur_start = i~~		print("Rezultat incorect!")
	~~cur_end = i~~
	~~cur_len = 1~~

	~~with open~~("~~secvcresc.out", "w") as fout:~~
	~~fout.write(f"{max_start + 1} {max_end + 1}\n~~") ~~# adăugăm 1 la indici pentru a fi 1-indexați~~





	</syntaxhighlight>		</syntaxhighlight>
			== Explicatie Rezolvare ==
			Pentru a rezolva această problemă, putem parcurge vectorul și ține în variabila lungime lungimea secvenței curente. De asemenea, putem ține și variabilele start și end care reprezintă indicele de început și sfârșit al secvenței curente. Dacă găsim o valoare mai mare decât precedenta, atunci lungimea secvenței crește și actualizăm end cu indicele curent. Dacă găsim o valoare mai mică sau egală cu precedenta, atunci secvența curentă se termină și verificăm dacă este mai lungă decât cea maximă găsită până acum. Dacă da, actualizăm variabilele max_start, max_end și max_length

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/181/secvcresc 0181 - SecvCresc] ---- == Cerinţa == Se dau n numere naturale, reprezentând elementele unui vector. Determinați cea mai lungă secvență de elemente ordonate strict crescător din vector. Dacă există mai multe astfel de secvențe se va determina cea mai din stânga. == Date de intrare == Fișierul de intrare secvcresc.in conține numărul n și n valori naturale, reprezentând elementele vectorului. Valorile din fi...

2023-03-21T21:44:35Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/181/secvcresc 0181 - SecvCresc] ---- == Cerinţa == Se dau n numere naturale, reprezentând elementele unui vector. Determinați cea mai lungă secvență de elemente ordonate strict crescător din vector. Dacă există mai multe astfel de secvențe se va determina cea mai din stânga. == Date de intrare == Fișierul de intrare secvcresc.in conține numărul n și n valori naturale, reprezentând elementele vectorului. Valorile din fi...

New page

Sursa: [https://www.pbinfo.ro/probleme/181/secvcresc 0181 - SecvCresc]
----
== Cerinţa ==
Se dau n numere naturale, reprezentând elementele unui vector. Determinați cea mai lungă secvență de elemente ordonate strict crescător din vector. Dacă există mai multe astfel de secvențe se va determina cea mai din stânga.

== Date de intrare ==
Fișierul de intrare secvcresc.in conține numărul n și n valori naturale, reprezentând elementele vectorului. Valorile din fișier pot fi dispuse pe mai multe linii.

== Date de ieșire ==
Fișierul de ieșire secvcresc.out va conține pe prima linie numerele st și dr, reprezentând indicii de început și de sfârșit ai secvenței determinate.

== Restricţii şi precizări ==
* 0 < n ≤ 10.000
* elementele vectorului vor fi mai mici decât 1.000.000 și sunt numerotate de la 1
== Exemplu ==
; Intrare
: 9
: 2 6 4 5 8 9 6 3 4
; Ieșire
: 3 6

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0181 - SecvCresc

with open("secvcresc.in") as fin:
n = int(fin.readline())
v = []
for _ in range(n):
v += list(map(int, fin.readline().split()))

max_start, max_end = 0, 0 # indicii de început și sfârșit ai secvenței maximale
cur_start, cur_end = 0, 0 # indicii de început și sfârșit ai secvenței crescătoare curente
max_len = 1 # lungimea maximă a secvenței crescătoare
cur_len = 1 # lungimea secvenței crescătoare curente

for i in range(1, n):
if v[i] > v[i - 1]:
cur_len += 1
cur_end = i
if cur_len > max_len:
max_start = cur_start
max_end = cur_end
max_len = cur_len
else:
cur_start = i
cur_end = i
cur_len = 1

with open("secvcresc.out", "w") as fout:
fout.write(f"{max_start + 1} {max_end + 1}\n") # adăugăm 1 la indici pentru a fi 1-indexați

</syntaxhighlight>