3796 - qtsume - Revision history

Flaviu at 21:00, 14 May 2023

2023-05-14T21:00:29Z

← Older revision		Revision as of 21:00, 14 May 2023
Line 53:		Line 53:
	# 3796 - qtsume		# 3796 - qtsume

	def ~~calc_sum~~(a, x, y):		def validate_input(N, Q, A, intrebari):
	~~sum~~ = 0		if not (1 <= N <= 100000 and 1 <= Q <= 100000):
	for i in range(x, y+1):		return False
	~~sum~~ += (i-x+1)*a[i-1]		for a in A:
	return ~~sum~~		if not (1 <= a <= 1000000):
			return False
			for x, y in intrebari:
			if not (1 <= x <= y <= N):
			return False
			return True

			def solve(N, A, intrebari):
			result = []
			for x, y in intrebari:
			s = 0
			for i in range(x-1, y):
			s += (i-x+2) * A[i]
			result.append(s)
			return result

	if __name__ == "__main__":		if __name__ == "__main__":
	# ~~Citirea datelor~~ de intrare		# Citire date de intrare
	n = int(~~input~~())		with open("qtsume.in", "r") as fin:
	a = list(map(int, ~~input~~().split()))		N = int(fin.readline().strip())
	q = int(~~input~~())		A = list(map(int, fin.readline().split()))
	~~queries~~ = []		Q = int(fin.readline().strip())
	~~for i in range~~(~~q):~~		intrebari = [tuple(map(int, line.strip().split())) for line in fin.readlines()]
	~~x, y =~~ map(int, ~~input~~().split())
	~~queries~~.~~append~~(~~(x, y)~~)

	# ~~Verificarea datelor~~ de intrare		# Verificare date de intrare
	if ~~n <= 0 or n > 100000 or q <= 0 or q > 100000~~:		if not validate_input(N, Q, A, intrebari):
	~~print~~("Datele nu corespund restricțiilor impuse.")		with open("qtsume.out", "w") as fout:
			fout.write("Datele nu corespund restricțiilor impuse.")
	else:		else:
	~~for x, y in queries:~~		# Rezolvare problema
	~~if x < 1 or x > n or y < 1 or y > n or x > y:~~		result = solve(N, A, intrebari)
	~~print("Datele nu corespund restricțiilor impuse.")~~
	~~break~~
	~~else:~~
	~~print("Datele sunt introduse corect.")~~
	~~print(calc_sum~~(a, x, y))

			# Scriere rezultat
			with open("qtsume.out", "w") as fout:
			fout.write("Datele sunt introduse corect.\n")
			for s in result:
			fout.write(str(s) + "\n")


Line 86:		Line 99:
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	Funcția ~~calc_sum~~ primește ca ~~argumente~~ vectorul a și ~~intervalul [x, y]~~ și ~~calculează suma cerută, iterând prin fiecare element din interval~~ și ~~aplicând formula specificată~~ în ~~cerință~~.		Funcția validate_input(N, Q, A, intrebari) primește ca parametrii numărul de elemente din vectorul A, numărul de întrebări, vectorul A și o listă cu perechi de întrebări. Funcția verifică dacă datele de intrare corespund restricțiilor impuse și returnează True dacă da și False în caz contrar.

	~~În blocul if __name__ == "__main__": citim datele~~ de ~~intrare~~ și ~~le verificăm. Dacă datele sunt introduse corect, iterăm prin fiecare pereche~~ de întrebări și ~~calculăm suma cerută, afișând-~~o ~~pe ecran~~.		Funcția solve(N, A, intrebari) primește ca parametrii numărul de elemente din vectorul A, vectorul A și o listă cu perechi de întrebări. Funcția rezolvă problema conform cerințelor și returnează o listă cu valorile cerute pentru fiecare întrebare.

	~~Pentru verificarea datelor~~ de intrare~~, folosim condițiile specificate în cerință~~ și ~~verificăm~~ dacă ~~valorile pentru x~~ și y se ~~află~~ în ~~intervalul [1, n] și x ≤ y~~. ~~Dacă datele nu corespund restricțiilor~~, ~~afișăm~~ un mesaj de ~~eroare și oprimm executarea~~.		În if __name__ == "__main__": se citesc datele de intrare din fișierul "qtsume.in" și se verifică dacă acestea sunt corecte folosind funcția validate_input(). În cazul în care datele sunt corecte, se rezolvă problema cu ajutorul funcției solve() și se scrie rezultatul în fișierul "qtsume.out". În caz contrar, se scrie un mesaj corespunzător în fișierul de ieșire.

Flaviu at 22:34, 13 May 2023

2023-05-13T22:34:55Z

← Older revision		Revision as of 22:34, 13 May 2023
Line 18:		Line 18:
	* 1 ≤ A[i] ≤ 1.000.000		* 1 ≤ A[i] ≤ 1.000.000
	* 1 ≤ x ≤ y ≤ N		* 1 ≤ x ≤ y ≤ N

			== Exemplu 1 ==
	; Intrare		; Intrare
	: 5		: 5
Line 26:		Line 28:
	: 2 4		: 2 4
	; Ieșire		; Ieșire
	~~: Datele nu corespund restricțiilor impuse.~~		: Datele sunt introduse corect.
	: Datele sunt introduse ~~correct~~.		: : 5
	: 5
	: 48		: 48
	: 14		: 14

			== Exemplu 2 ==
			; Intrare
			: 100000
			: 1 2 3 4 5 6 7 8 9 10
			: 100000
			: 1 100001
			: 1 50000
			: 50001 100000
			: 3 3
			: 50000 50000
			: 100000 100000
			; Ieșire
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==
Line 37:		Line 53:
	# 3796 - qtsume		# 3796 - qtsume

	def ~~citire_date~~():		def calc_sum(a, x, y):
			sum = 0
			for i in range(x, y+1):
			sum += (i-x+1)*a[i-1]
			return sum

			if __name__ == "__main__":
			# Citirea datelor de intrare
	n = int(input())		n = int(input())
	v = list(map(int, input().split()))		a = list(map(int, input().split()))
	q = int(input())		q = int(input())
	~~intrebari~~ = []		queries = []
	for i in range(q):		for i in range(q):
	x, y = map(int, input().split())		x, y = map(int, input().split())
	~~intrebari~~.append((x, y))		queries.append((x, y))
	~~return n, v, q, intrebari~~

	~~def validare(n, v, q, intrebari):~~		# Verificarea datelor de intrare
	if ~~len(v) !=~~ n:		if n <= 0 or n > 100000 or q <= 0 or q > 100000:
	~~return False~~		print("Datele nu corespund restricțiilor impuse.")
	~~for x in v:~~		else:
	~~if x~~ < 1 or x > ~~1000000:~~		for x, y in queries:
	~~return False~~		if x < 1 or x > n or y < 1 or y > n or x > y:
	if q < 1 or q > 100000:		print("Datele nu corespund restricțiilor impuse.")
	~~return False~~		break
	for x, y in ~~intrebari~~:		else:
	if x < 1 or x > n or y < 1 or y > n or x > y:		print("Datele sunt introduse corect.")
	~~return False~~		print(calc_sum(a, x, y))
	~~return True~~

	~~def calc_suma~~(~~x, y, v~~):
	~~suma = 0~~
	~~for i in range~~(x-1, y):
	~~suma += (i-x+1+1~~)*v[i]
	~~return suma~~

	~~if __name__ == '__main__':~~
	~~n, v, q, intrebari = citire_date()~~
	~~if validare(n, v, q, intrebari):~~
	~~print("Datele sunt introduse corect.")~~
	~~for x, y in intrebari:~~
	~~suma = calc_suma(x, y, v)~~
	~~print(suma)~~
	~~else:~~
	~~print("Datele nu corespund restricțiilor impuse.")~~


Line 80:		Line 86:
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	Funcția ~~citire_date() citește datele de intrare~~ și ~~le returnează sub forma unor variabile: n pentru numărul de elemente din vectorul A~~, ~~v pentru vectorul A, q pentru numărul de întrebări~~ și ~~intrebari pentru o listă de tupluri~~, fiecare ~~tuplu reprezentând o întrebare~~.		Funcția calc_sum primește ca argumente vectorul a și intervalul [x, y] și calculează suma cerută, iterând prin fiecare element din interval și aplicând formula specificată în cerință.
	~~Funcția validare() verifică dacă~~ datele de intrare ~~respectă restricțiile cerute în enunț, returnând True dacă~~ datele sunt ~~valide~~ și ~~False în caz contrar.~~
	~~Funcția calc_suma() calculează~~ suma cerută ~~pentru~~ o ~~întrebare,~~ pe ~~baza formulei din enunț~~.		În blocul if __name__ == "__main__": citim datele de intrare și le verificăm. Dacă datele sunt introduse corect, iterăm prin fiecare pereche de întrebări și calculăm suma cerută, afișând-o pe ecran.
	~~În funcția main()~~, ~~se verifică~~ dacă ~~datele de intrare sunt valide~~ și se ~~afișează mesajul corespunzător~~. Dacă datele ~~sunt valide~~, ~~se calculează suma pentru fiecare întrebare~~ și ~~se afișează rezultatul~~.
			Pentru verificarea datelor de intrare, folosim condițiile specificate în cerință și verificăm dacă valorile pentru x și y se află în intervalul [1, n] și x ≤ y. Dacă datele nu corespund restricțiilor, afișăm un mesaj de eroare și oprimm executarea.

Flaviu at 18:53, 27 April 2023

2023-04-27T18:53:11Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire qtsume.out va conține pe ~~Q linii~~, pe ~~linia i aflându-~~se ~~răspunsul la a i-a întrebare în ordinea citirii~~.		Fișierul de ieșire qtsume.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 26:
	: 2 4		: 2 4
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 5		: 5
	: 48		: 48
Line 32:		Line 37:
	# 3796 - qtsume		# 3796 - qtsume

	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):		q = int(input())
	~~sir.append~~(int(~~input~~()))		intrebari = []
	return ~~sir~~		for i in range(q):
			x, y = map(int, input().split())
			intrebari.append((x, y))
			return n, v, q, intrebari

	def ~~numara_secvente_crescatoare~~(~~sir~~):		def validare(n, v, q, intrebari):
	~~numar_secvente~~ = 0		if len(v) != n:
	~~lungime_maxima = 1~~		return False
	~~lungime_curenta = 1~~		for x in v:
	for i in ~~range(1, len(sir))~~:		if x < 1 or x > 1000000:
	if ~~sir[i] >= sir[i-~~1]:		return False
	~~lungime_curenta += 1~~		if q < 1 or q > 100000:
	~~else:~~		return False
	~~if lungime_curenta~~ > ~~lungime_maxima~~:		for x, y in intrebari:
	~~lungime_maxima = lungime_curenta~~		if x < 1 or x > n or y < 1 or y > n or x > y:
	~~numar_secvente = 1~~		return False
	~~elif lungime_curenta == lungime_maxima:~~		return True
	~~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~~):		def calc_suma(x, y, v):
	~~assert len~~(~~sir~~) ~~> 0~~		suma = 0
	~~assert numar_secvente >~~= 0		for i in range(x-1, y):
			suma += (i-x+1+1)*v[i]
			return suma

			if __name__ == '__main__':
			n, v, q, intrebari = citire_date()
			if validare(n, v, q, intrebari):
			print("Datele sunt introduse corect.")
			for x, y in intrebari:
			suma = calc_suma(x, y, v)
			print(suma)
			else:
			print("Datele nu corespund restricțiilor impuse.")

	~~if __name__ == "__main__":~~
	~~sir = citeste_date_intrare()~~
	~~numar_secvente = numara_secvente_crescatoare(sir)~~
	~~valideaza(sir, numar_secvente)~~
	~~print(numar_secvente)~~

	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția ~~read_input~~ citește datele de intrare și le returnează sub forma ~~unei tuple ce conține~~ n, a și ~~queries. solve primește aceste date și calculează suma~~ pentru fiecare ~~interogare~~. Funcția ~~validate~~ verifică ~~că rezultatele obținute~~ sunt ~~corecte~~. În ~~cele din urmă, în~~ funcția main, ~~citim~~ datele de intrare, ~~apelăm funcția solve, validăm rezultatele~~ și ~~le afișăm~~.
			Funcția citire_date() citește datele de intrare și le returnează sub forma unor variabile: n pentru numărul de elemente din vectorul A, v pentru vectorul A, q pentru numărul de întrebări și intrebari pentru o listă de tupluri, fiecare tuplu reprezentând o întrebare.
			Funcția validare() verifică dacă datele de intrare respectă restricțiile cerute în enunț, returnând True dacă datele sunt valide și False în caz contrar.
			Funcția calc_suma() calculează suma cerută pentru o întrebare, pe baza formulei din enunț.
			În funcția main(), se verifică dacă datele de intrare sunt valide și se afișează mesajul corespunzător. Dacă datele sunt valide, se calculează suma pentru fiecare întrebare și se afișează rezultatul.

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3796/qtsume 3796 - qtsume] ---- == Cerinţa == Se dă un vector A cu N numere naturale. Pentru Q întrebări de forma (x, y) aflați rezultatul sumei A[x] + 2 * A[x + 1] + ... + (y - x + 1) * A[y]. == Date de intrare == Fișierul de intrare qtsume.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații, reprezentând vectorul A. Pe următoarea linie se află numărul Q. Urmează Q linii, pe fi...

2023-04-17T20:30:40Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3796/qtsume 3796 - qtsume] ---- == Cerinţa == Se dă un vector A cu N numere naturale. Pentru Q întrebări de forma (x, y) aflați rezultatul sumei A[x] + 2 * A[x + 1] + ... + (y - x + 1) * A[y]. == Date de intrare == Fișierul de intrare qtsume.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații, reprezentând vectorul A. Pe următoarea linie se află numărul Q. Urmează Q linii, pe fi...

New page

Sursa: [https://www.pbinfo.ro/probleme/3796/qtsume 3796 - qtsume]
----
== Cerinţa ==
Se dă un vector A cu N numere naturale. Pentru Q întrebări de forma (x, y) aflați rezultatul sumei A[x] + 2 * A[x + 1] + ... + (y - x + 1) * A[y].

== Date de intrare ==
Fișierul de intrare qtsume.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații, reprezentând vectorul A. Pe următoarea linie se află numărul Q. Urmează Q linii, pe fiecare linie se află două numere naturale separate printr-un spațiu reprezentând x și y.

== Date de ieșire ==
Fișierul de ieșire qtsume.out va conține pe Q linii, pe linia i aflându-se răspunsul la a i-a întrebare în ordinea citirii.

== Restricţii şi precizări ==
* 1 ≤ N, Q ≤ 100.000
* 1 ≤ A[i] ≤ 1.000.000
* 1 ≤ x ≤ y ≤ N
; Intrare
: 5
: 3 1 2 3 5
: 3
: 1 2
: 1 5
: 2 4
; Ieșire
: 5
: 48
: 14

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3796 - qtsume

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 read_input citește datele de intrare și le returnează sub forma unei tuple ce conține n, a și queries. solve primește aceste date și calculează suma pentru fiecare interogare. Funcția validate verifică că rezultatele obținute sunt corecte. În cele din urmă, în funcția main, citim datele de intrare, apelăm funcția solve, validăm rezultatele și le afișăm.