3796 - qtsume: Diferență între versiuni
(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...) |
Fără descriere a modificării |
||
Linia 9: | Linia 9: | ||
== Date de ieșire == | == Date de ieșire == | ||
Fișierul de ieșire qtsume.out va conține pe | 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 == | ||
Linia 23: | Linia 26: | ||
: 2 4 | : 2 4 | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | |||
: Datele sunt introduse correct. | |||
: 5 | : 5 | ||
: 48 | : 48 | ||
Linia 32: | Linia 37: | ||
# 3796 - qtsume | # 3796 - qtsume | ||
def | def citire_date(): | ||
n = int(input()) | n = int(input()) | ||
v = list(map(int, input().split())) | |||
for i in range( | q = int(input()) | ||
intrebari = [] | |||
return | for i in range(q): | ||
x, y = map(int, input().split()) | |||
intrebari.append((x, y)) | |||
return n, v, q, intrebari | |||
def | def validare(n, v, q, intrebari): | ||
if len(v) != n: | |||
return False | |||
for x in v: | |||
for | if x < 1 or x > 1000000: | ||
if | return False | ||
if q < 1 or q > 100000: | |||
return False | |||
for x, y in intrebari: | |||
if x < 1 or x > n or y < 1 or y > n or x > y: | |||
return False | |||
return True | |||
if | |||
return | |||
def | 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.") | |||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | == Explicatie Rezolvare == | ||
Funcția | |||
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. |
Versiunea de la data 27 aprilie 2023 18:53
Sursa: 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
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
- 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
- Datele nu corespund restricțiilor impuse.
- Datele sunt introduse correct.
- 5
- 48
- 14
Rezolvare
Rezolvare ver. 1
# 3796 - qtsume
def citire_date():
n = int(input())
v = list(map(int, input().split()))
q = int(input())
intrebari = []
for i in range(q):
x, y = map(int, input().split())
intrebari.append((x, y))
return n, v, q, intrebari
def validare(n, v, q, intrebari):
if len(v) != n:
return False
for x in v:
if x < 1 or x > 1000000:
return False
if q < 1 or q > 100000:
return False
for x, y in intrebari:
if x < 1 or x > n or y < 1 or y > n or x > y:
return False
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.")
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 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.