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.")

</syntaxhighlight>

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.