3796 - qtsume

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

Exemplu 1

Intrare

5

3 1 2 3 5

3

1 2

1 5

2 4

Ieșire

Datele sunt introduse corect.

: 5

48

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 ver. 1

<syntaxhighlight lang="python" line>

1. 3796 - qtsume

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())
   a = list(map(int, input().split()))
   q = int(input())
   queries = []
   for i in range(q):
       x, y = map(int, input().split())
       queries.append((x, y))

   # Verificarea datelor de intrare
   if n <= 0 or n > 100000 or q <= 0 or q > 100000:
       print("Datele nu corespund restricțiilor impuse.")
   else:
       for x, y in queries:
           if x < 1 or x > n or y < 1 or y > n or x > y:
               print("Datele nu corespund restricțiilor impuse.")
               break
           else:
               print("Datele sunt introduse corect.")
               print(calc_sum(a, x, y))

</syntaxhighlight>

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ță.

Î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.

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.