0299 - SumeSecv - Revision history

Flaviu at 20:46, 14 May 2023

2023-05-14T20:46:57Z

← Older revision		Revision as of 20:46, 14 May 2023
Line 38:		Line 38:
	: 2 4		: 2 4
	; Ieșire		; Ieșire
	: Datele ~~sunt introduse correct~~		: Datele nu corespund restrictiilor impuse
	~~: sumesecv.out~~
	~~: 1 2 3 4 5~~
	~~: 2~~
	~~: 1 5~~
	~~: 2 4~~

	== Rezolvare ==		== Rezolvare ==
Line 50:		Line 46:
	# 0304 - Secvente		# 0304 - Secvente

	def ~~calculeaza_suma~~(~~secventa~~):		def calculeaza_suma_secvente(n, v, m, perechi):
	suma = 0		for pereche in perechi:
	for x in ~~secventa~~:		i, j = pereche
	~~suma +~~= x		suma = 0
	return ~~suma~~		for k in range(i, j + 1):
			suma += v[k - 1]
			print(suma, end=' ')

			def valideaza_datele(n, v, m, perechi):
			if n != len(v):
			return False
			for i, j in perechi:
			if not (1 <= i < j <= n):
			return False
			return True

	if __name__ == '__main__':		if __name__ == '__main__':
	~~# Citire date de intrare~~		with open('sumesecv.in', 'r') as f:
	~~try:~~		n = int(f.readline())
	with open('sumesecv.in', 'r') as f:		v = list(map(int, f.readline().split()))
	n = int(f.readline~~().strip~~())		m = int(f.readline())
	v = list(map(int, f.readline().split()))		perechi = [tuple(map(int, f.readline().split())) for _ in range(m)]
	m = int(f.readline~~().strip~~())		if valideaza_datele(n, v, m, perechi):
	perechi = []		print('Datele sunt introduse corect.')
	~~for i in range(m):~~		calculeaza_suma_secvente(n, v, m, perechi)
	~~perechi.append(list~~(map(int, f.readline().split())))		else:
	~~except:~~		print('Datele nu corespund restricțiilor impuse.')
	~~print~~(~~"Datele nu corespund restricțiilor impuse."~~)
	~~exit()~~

	~~# Verificare restricții~~
	if n ~~< 1 or n > 100 or~~ m ~~< 1 or m > 100~~:
	print("Datele ~~nu corespund restricțiilor impuse~~.")
	~~exit~~()
	~~for x in~~ v:
	~~if x >= 1000:~~
	~~print("Datele nu corespund restricțiilor impuse.")~~
	~~exit(~~)
	~~for p in perechi~~:
	~~if p[0] < 1 or p[0] >= p[1] or p[1] > n:~~
	print("Datele nu corespund restricțiilor impuse.")
	~~exit()~~

	~~# Calculare sume secvențe~~
	~~sume = []~~
	~~for p in perechi:~~
	~~sume.append(calculeaza_suma(v[p[0]-1:p[1]]))~~

	~~# Scriere rezultat~~
	~~print("Datele sunt introduse corect.")~~
	~~with open('sumesecv.out', 'w') as f:~~
	~~for s in sume:~~
	~~f.write(str(s) + '~~ ')


Line 98:		Line 78:

	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~Funcția solve(input_data: str) -> str:~~
	Această funcție primește ca argument un șir de caractere input_data care conține datele de intrare ale problemei și trebuie să returneze un șir de caractere care conține datele de ieșire cerute de problema.
	În cadrul acestei funcții, mai întâi se parsează datele de intrare primite ca argument, adică se extrag valorile numerice și se stochează în variabile corespunzătoare. Apoi, se calculează suma elementelor din secvența determinată de fiecare pereche de indici și se stochează valorile calculate într-o listă.
	~~La final, se construiește șirul de caractere de ieșire prin concatenarea string-urilor corespunzătoare valorilor calculate și se returnează acest șir de caractere.~~

	Funcția ~~main~~():		Funcția calculeaza_suma_secvente primește ca parametri numărul de elemente din vector (n), vectorul (v), numărul de perechi de indici (m) și o listă de perechi de indici (perechi). Aceasta parcurge lista de perechi de indici și pentru fiecare pereche calculează suma elementelor din secvența determinată de indicii respectivi.
	~~Această funcție este folosită pentru a verifica~~ dacă datele de intrare sunt ~~introduse corect~~. ~~În cazul în care~~ datele sunt introduse corect, se ~~apelează funcția solve(input_data: str) -> str~~ pentru ~~a calcula rezultatul și a afișa datele~~ de ~~ieșire~~. ~~În caz contrar~~, se afișează ~~un mesaj de eroare pe ecran~~. ~~Această funcție primește datele de intrare de la utilizator prin intermediul funcției input()~~.
			Funcția valideaza_datele primește ca parametri numărul de elemente din vector (n), vectorul (v), numărul de perechi de indici (m) și o listă de perechi de indici (perechi). Aceasta verifică dacă datele introduse sunt valide, adică dacă numărul de elemente din vector corespunde cu n, iar fiecare pereche de indici are valorile corecte.

			În funcția main, se deschide fișierul de intrare, se citesc datele și se verifică dacă sunt valide prin apelarea funcției valideaza_datele. Dacă datele sunt valide, se afișează mesajul "Datele sunt introduse corect." și se calculează suma pentru fiecare pereche de indici prin apelarea funcției calculeaza_suma_secvente. Dacă datele nu sunt valide, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

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

2023-05-14T20:16:05Z

Date de ieșire

← Older revision		Revision as of 20:16, 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."''', apoi fișierul sumesecv.out ''' numărul n~~, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', reprezentând valoarea cerută~~. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi fișierul sumesecv.out conține ''' numărul n. Î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-14T20:14:19Z

Date de ieșire

← Older revision		Revision as of 20:14, 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."''', apoi fișierul ''' numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi fișierul sumesecv.out ''' numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', 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-14T20:13:48Z

Date de ieșire

← Older revision		Revision as of 20:13, 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."''', apoi ~~pe un rând nou~~ ''' numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi fișierul ''' numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', 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-14T20:07:14Z

Date de ieșire

← Older revision		Revision as of 20:07, 14 May 2023
Line 8:		Line 8:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fişierul de ieşire sumesecv,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 '''~~prima linie~~ numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', 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 ''' numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', 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 22:14, 13 May 2023

2023-05-13T22:14:24Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fişierul de ieşire ~~secvente.~~out va conţine Dacă datele sunt introduse corect, pe ecran se va afișa:		Fişierul de ieşire sumesecv,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 '''prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', 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 '''prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

Line 18:		Line 18:
	== Exemplu 1 ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: ~~secvente~~.in		:sumesecv.in
	: 10		: 10
	: 5 5 1 3 6 4 1 2 10 6		: 5 5 1 3 6 4 1 2 10 6
Line 26:		Line 26:
	: 6 10		: 6 10
	; Ieșire		; Ieșire
	~~: secvente.out~~
	: Datele sunt introduse correct		: Datele sunt introduse correct
			: sumesecv.out
	: 13 19 23		: 13 19 23

	== Exemplu 2 ==		== Exemplu 2 ==
	; Intrare		; Intrare
	: ~~secvente~~.in		: sumesecv.in
	: 10		: 5
	: ~~5 5~~ 1 3 6 4 ~~1 2 10 6~~		: 1 2 3 4 5
	: 3		: 2
	: 5 8		: 1 5
	: 2 6		: 2 4
	~~: 6 10~~
	; Ieșire		; Ieșire
	: ~~secvente~~.out		: Datele sunt introduse correct
	: ~~Datele nu corespund restricțiilor impuse.~~		: sumesecv.out
	: 1 2 8		: 1 2 3 4 5
			: 2
			: 1 5
			: 2 4

	== Rezolvare ==		== Rezolvare ==
Line 49:		Line 51:
	# 0304 - Secvente		# 0304 - Secvente

	def ~~citire_date~~():		def calculeaza_suma(secventa):
	~~n = int(input())~~
	~~v = list(map(int, input().split()))~~
	~~m = int(input())~~
	~~perechi = []~~
	~~for i in range(m):~~
	~~a, b = map(int, input().split())~~
	~~perechi.append((a, b))~~
	~~return n, v, m, perechi~~

	~~def suma_secventa(n, v, a, b~~):
	suma = 0		suma = 0
	for i in ~~range(a-1, b)~~:		for x in secventa:
	suma += ~~v[i]~~		suma += x
	return suma		return suma

	if __name__ == '__main__':		if __name__ == '__main__':
	n, v, ~~m, perechi = citire_date~~()		# Citire date de intrare
	~~if 1 <= n <= 100 and 1 <=~~ m <= ~~100:~~		try:
	~~print~~(~~"Datele sunt introduse corect~~.")		with open('sumesecv.in', 'r') as f:
	for ~~a, b~~ in ~~perechi~~:		n = int(f.readline().strip())
	~~print~~(~~suma_secventa~~(n, ~~v, a, b~~))		v = list(map(int, f.readline().split()))
	~~else~~:		m = int(f.readline().strip())
			perechi = []
			for i in range(m):
			perechi.append(list(map(int, f.readline().split())))
			except:
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
			exit()

			# Verificare restricții
			if n < 1 or n > 100 or m < 1 or m > 100:
			print("Datele nu corespund restricțiilor impuse.")
			exit()
			for x in v:
			if x >= 1000:
			print("Datele nu corespund restricțiilor impuse.")
			exit()
			for p in perechi:
			if p[0] < 1 or p[0] >= p[1] or p[1] > n:
			print("Datele nu corespund restricțiilor impuse.")
			exit()

			# Calculare sume secvențe
			sume = []
			for p in perechi:
			sume.append(calculeaza_suma(v[p[0]-1:p[1]]))

			# Scriere rezultat
			print("Datele sunt introduse corect.")
			with open('sumesecv.out', 'w') as f:
			for s in sume:
			f.write(str(s) + ' ')


	</syntaxhighlight>		</syntaxhighlight>

	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~citire_date citește~~ datele de intrare ~~din consolă~~ și ~~le returnează sub formă~~ de ~~tuplu~~.		Funcția solve(input_data: str) -> str:
	~~Funcția suma_secventa primește un vector v~~, ~~un interval [a~~, b] și calculează suma elementelor din secvența ~~din vectorul v care începe la poziția a~~ și se ~~termină la poziția b~~.		Această funcție primește ca argument un șir de caractere input_data care conține datele de intrare ale problemei și trebuie să returneze un șir de caractere care conține datele de ieșire cerute de problema.
	~~În funcția principală (__main__)~~, se ~~citesc datele~~ de ~~intrare~~ și se ~~verifică~~ dacă ~~respectă restricțiile impuse~~. ~~Dacă da, se afișează mesajul "Datele~~ sunt introduse corect~~." și~~ se ~~calculează suma~~ pentru ~~fiecare pereche~~ de ~~indici~~. ~~Dacă nu~~, se afișează ~~mesajul "Datele nu corespund restricțiilor impuse~~.".		În cadrul acestei funcții, mai întâi se parsează datele de intrare primite ca argument, adică se extrag valorile numerice și se stochează în variabile corespunzătoare. Apoi, se calculează suma elementelor din secvența determinată de fiecare pereche de indici și se stochează valorile calculate într-o listă.
			La final, se construiește șirul de caractere de ieșire prin concatenarea string-urilor corespunzătoare valorilor calculate și se returnează acest șir de caractere.

			Funcția main():
			Această funcție este folosită pentru a verifica dacă datele de intrare sunt introduse corect. În cazul în care datele sunt introduse corect, se apelează funcția solve(input_data: str) -> str pentru a calcula rezultatul și a afișa datele de ieșire. În caz contrar, se afișează un mesaj de eroare pe ecran. Această funcție primește datele de intrare de la utilizator prin intermediul funcției input().

Flaviu at 07:44, 3 May 2023

2023-05-03T07:44:26Z

← Older revision		Revision as of 07:44, 3 May 2023
Line 9:		Line 9:
	== Date de ieșire ==		== Date de ieșire ==
	Fişierul de ieşire secvente.out va conţine Dacă datele sunt introduse corect, pe ecran se va afișa:		Fişierul de ieşire secvente.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."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou '''prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


Line 16:		Line 16:
	* elementele vectorului vor fi mai mici decât 1000		* elementele vectorului vor fi mai mici decât 1000
	* 1 ≤ m ≤ 100		* 1 ≤ m ≤ 100
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: secvente.in
	: 10		: 10
	: 5 5 1 3 6 4 1 2 10 6		: 5 5 1 3 6 4 1 2 10 6
Line 25:		Line 26:
	: 6 10		: 6 10
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: secvente.out
	: Datele sunt introduse correct		: Datele sunt introduse correct
	: 13 19 23		: 13 19 23

			== Exemplu 2 ==
			; Intrare
			: secvente.in
			: 10
			: 5 5 1 3 6 4 1 2 10 6
			: 3
			: 5 8
			: 2 6
			: 6 10
			; Ieșire
			: secvente.out
			: Datele nu corespund restricțiilor impuse.
			: 1 2 8

	== Rezolvare ==		== Rezolvare ==

Flaviu at 18:42, 27 April 2023

2023-04-27T18:42:29Z

← Older revision		Revision as of 18:42, 27 April 2023
Line 8:		Line 8:

	== Date de ieșire ==		== Date de ieșire ==
	Fişierul de ieşire ~~sumesecv~~.out va conţine pe ~~prima linie cele m sume determinate~~, ~~separate prin câte~~ un ~~spațiu~~.		Fişierul de ieşire secvente.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 23:		Line 25:
	: 6 10		: 6 10
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct
	: 13 19 23		: 13 19 23

Line 30:		Line 34:
	# 0304 - Secvente		# 0304 - Secvente

	def ~~citeste_date_intrare~~():		def citire_date():
	n = int(input())		n = int(input())
	~~sir~~ = []		v = list(map(int, input().split()))
	for i in range(n):		m = int(input())
	~~sir.append~~(int(~~input~~()))		perechi = []
	return ~~sir~~		for i in range(m):
			a, b = map(int, input().split())
			perechi.append((a, b))
			return n, v, m, perechi

	def ~~numara_secvente_crescatoare~~(~~sir~~):		def suma_secventa(n, v, a, b):
	~~numar_secvente~~ = 0		suma = 0
	~~lungime_maxima = 1~~		for i in range(a-1, b):
	~~lungime_curenta = 1~~		suma += v[i]
	for i in range(1, ~~len(sir)~~):		return suma
	~~if sir[i] >~~= ~~sir~~[i-1]:
	~~lungime_curenta += 1~~
	~~else:~~
	~~if lungime_curenta > lungime_maxima:~~
	~~lungime_maxima = lungime_curenta~~
	~~numar_secvente = 1~~
	~~elif lungime_curenta == lungime_maxima:~~
	~~numar_secvente += 1~~
	~~lungime_curenta = 1~~
	~~if lungime_curenta > lungime_maxima:~~
	~~lungime_maxima = lungime_curenta~~
	~~numar_secvente = 1~~
	~~elif lungime_curenta == lungime_maxima:~~
	~~numar_secvente += 1~~
	return ~~numar_secvente~~

	~~def valideaza(sir, numar_secvente):~~		if __name__ == '__main__':
	~~assert len(sir) > 0~~		n, v, m, perechi = citire_date()
	~~assert numar_secvente >= 0~~		if 1 <= n <= 100 and 1 <= m <= 100:
			print("Datele sunt introduse corect.")
	if __name__ == "__main__":		for a, b in perechi:
	~~sir~~ = ~~citeste_date_intrare~~()		print(suma_secventa(n, v, a, b))
	~~numar_secvente~~ = ~~numara_secvente_crescatoare~~(~~sir~~)		else:
	~~valideaza~~(~~sir~~, ~~numar_secvente~~)		print("Datele nu corespund restricțiilor impuse.")
	print(~~numar_secvente~~)

	</syntaxhighlight>		</syntaxhighlight>

	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~citeste_date_intrare primește~~ datele de intrare ~~de la tastatură~~ și le returnează sub ~~forma unei liste~~.		Funcția citire_date citește datele de intrare din consolă și le returnează sub formă de tuplu.
			Funcția suma_secventa primește un vector v, un interval [a, b] și calculează suma elementelor din secvența din vectorul v care începe la poziția a și se termină la poziția b.
	Funcția ~~numara_secvente_crescatoare~~ primește lista de numere și numără secvențele maximale cu elemente ordonate crescător din șirul dat. Algoritmul este simplu: parcurgem lista și ținem minte lungimea maximă a unei secvențe cu elemente ordonate crescător și numărul de astfel de secvențe găsite până în acel moment. Când întâlnim un ~~element mai mic decât cel precedent~~, ~~înseamnă că secvența curentă s-~~a ~~încheiat~~, ~~verificăm dacă are lungimea maximă~~ și ~~actualizăm numărul de secvențe dacă e cazul. La final mai facem o verificare dacă ultima secvență~~ a ~~fost maximă~~.		În funcția principală (__main__), se citesc datele de intrare și se verifică dacă respectă restricțiile impuse. Dacă da, se afișează mesajul "Datele sunt introduse corect." și se calculează suma pentru fiecare pereche de indici. Dacă nu, se afișează mesajul "Datele nu corespund restricțiilor impuse.".

	~~Funcția valideaza~~ verifică dacă ~~datele de ieșire~~ sunt ~~valide~~.

	~~În blocul if __name__ ==~~ "~~__main__": citim datele~~ de ~~intrare~~, ~~apelăm funcția numara_secvente_crescatoare și afișăm rezultatul~~.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/299/sumesecv - SumeSecv] ---- == Cerinţa == Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i
2023-04-17T20:13:18Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/299/sumesecv - SumeSecv] ---- == Cerinţa == Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i<j≤n. Să se determine, pentru fiecare pereche (i,j), suma elementelor din secvenţa determinată de i şi j. == Date de intrare == Fişierul de intrare sumesecv.in conţine pe prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține n...

New page
Sursa: [https://www.pbinfo.ro/probleme/299/sumesecv - SumeSecv]
----
== Cerinţa ==
Se dă un vector cu n elemente numere naturale, numerotate de la 1 la n, și m perechi de indici (i,j), cu 1≤i<j≤n. Să se determine, pentru fiecare pereche (i,j), suma elementelor din secvenţa determinată de i şi j.

== Date de intrare ==
Fişierul de intrare sumesecv.in conţine pe prima linie numărul n, iar pe a doua linie cele n elemente ale vectorului. Următoarea linie conține numărul m, iar următoarele m linii câte o pereche de indici i j.

== Date de ieșire ==
Fişierul de ieşire sumesecv.out va conţine pe prima linie cele m sume determinate, separate prin câte un spațiu.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100
* elementele vectorului vor fi mai mici decât 1000
* 1 ≤ m ≤ 100
== Exemplu ==
; Intrare
: 10
: 5 5 1 3 6 4 1 2 10 6
: 3
: 5 8
: 2 6
: 6 10
; Ieșire
: 13 19 23

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 0304 - Secvente

def citeste_date_intrare():
n = int(input())
sir = []
for i in range(n):
sir.append(int(input()))
return sir

def numara_secvente_crescatoare(sir):
numar_secvente = 0
lungime_maxima = 1
lungime_curenta = 1
for i in range(1, len(sir)):
if sir[i] >= sir[i-1]:
lungime_curenta += 1
else:
if lungime_curenta > lungime_maxima:
lungime_maxima = lungime_curenta
numar_secvente = 1
elif lungime_curenta == lungime_maxima:
numar_secvente += 1
lungime_curenta = 1
if lungime_curenta > lungime_maxima:
lungime_maxima = lungime_curenta
numar_secvente = 1
elif lungime_curenta == lungime_maxima:
numar_secvente += 1
return numar_secvente

def valideaza(sir, numar_secvente):
assert len(sir) > 0
assert numar_secvente >= 0

if name == "main":
sir = citeste_date_intrare()
numar_secvente = numara_secvente_crescatoare(sir)
valideaza(sir, numar_secvente)
print(numar_secvente)

</syntaxhighlight>

== Explicatie Rezolvare ==
Funcția citeste_date_intrare primește datele de intrare de la tastatură și le returnează sub forma unei liste.

Funcția numara_secvente_crescatoare primește lista de numere și numără secvențele maximale cu elemente ordonate crescător din șirul dat. Algoritmul este simplu: parcurgem lista și ținem minte lungimea maximă a unei secvențe cu elemente ordonate crescător și numărul de astfel de secvențe găsite până în acel moment. Când întâlnim un element mai mic decât cel precedent, înseamnă că secvența curentă s-a încheiat, verificăm dacă are lungimea maximă și actualizăm numărul de secvențe dacă e cazul. La final mai facem o verificare dacă ultima secvență a fost maximă.

Funcția valideaza verifică dacă datele de ieșire sunt valide.

În blocul if name == "main": citim datele de intrare, apelăm funcția numara_secvente_crescatoare și afișăm rezultatul.