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 validate_input(N, Q, A, intrebari):

   if not (1 <= N <= 100000 and 1 <= Q <= 100000):
       return False
   for a in A:
       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__":

   # Citire date de intrare
   with open("qtsume.in", "r") as fin:
       N = int(fin.readline().strip())
       A = list(map(int, fin.readline().split()))
       Q = int(fin.readline().strip())
       intrebari = [tuple(map(int, line.strip().split())) for line in fin.readlines()]

   # Verificare date de intrare
   if not validate_input(N, Q, A, intrebari):
       with open("qtsume.out", "w") as fout:
           fout.write("Datele nu corespund restricțiilor impuse.")
   else:
       # Rezolvare problema
       result = solve(N, A, intrebari)

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

</syntaxhighlight>

Explicatie Rezolvare

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.

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.

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