1933 - Sume2

Cerința

Fie N un numar natural și un șir de N numere naturale V[1], V[2], …, V[N]. Pentru M întrebări de forma (i,j), să se calculeze suma termenilor V[i], V[i + 1], …, V[j].

Date de intrare

Pe prima linie a fișierului sume2in.txt se găsește un număr natural N. Pe urmatoarea linie sunt N numere naturale, reprezentând valorile șirului V. Pe a treia linie se găsește un număr natural M reprezentând numărul de întrebări, iar pe următoarele M linii câte o pereche de numere (i,j), reprezentând o întrebare pentru care se cere să se calculeze suma V[i] + V[i + 1] + ... + V[j].

Date de ieșire

Pe prima linie din fişierul sume2out.txt se găseşte răspunsul la prima întrebare din fişierul de intrare, pe a doua linie se găseşte răspunsul la cea de-a doua întrebare, și așa mai departe.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 500.000
• 0 ≤ V[i] ≤ 1.000.000.000

Pentru 30% dintre teste N, M ≤ 1.000

Exemplul 1

sume2in.txt

4

1 2 3 4

2

1 3

2 4

sume2.out

Datele introduse corespund restricțiilor impuse.

6

9

Explicație

uma elementelor de pe pozițiile de la 1 la 3 este 6. Suma elementelor de pe pozițiile de la 2 la 4 este 9.

Exemplul 2

sume2in.txt

6

1 2 3 4 5 1000000001

2

1 3

2 4

sume2.out

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 1933 - Sume2

def validare(numarde_elemente, numarde_intrebari, sirul, intrebarii): # functia de validare a datelor de intrare

   if not (1 <= numarde_elemente <= 100000) or not (1 <= numarde_intrebari <= 500000):
       raise ValueError

   if len(sirul) != numarde_elemente or any(not (0 <= element <= 1000000000) for element in sirul):
       raise ValueError

   if any(not (1 <= i <= j <= numarde_elemente) for i, j in intrebarii):
       raise ValueError

   fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")

def calculeaza_sume(sirul, intrebarii): # functia de rezolvare

   for i, j in intrebarii:
       suma = sum(sirul[k - 1] for k in range(i, j + 1))
       fisier_iesire.write(f"{suma}\n")

if __name__ == '__main__':

   fisier_intrare = open("sume2in.txt", "r")         # declararea fisierelor
   fisier_iesire = open("sume2out.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       numar_elemente = int(fisier_intrare.readline())
       sir = list(map(int, fisier_intrare.readline().split()))
       numar_intrebari = int(fisier_intrare.readline())
       intrebari = [list(map(int, fisier_intrare.readline().split())) for _ in range(numar_intrebari)]

       validare(numar_elemente, numar_intrebari, sir, intrebari)                 # apelul functiei de validare
       calculeaza_sume(sir, intrebari)               # apelul functiei de rezolvare

   except ValueError:
       fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>