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 pe Q linii, pe linia i aflându-se răspunsul la a i-a întrebare în ordinea citirii.

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

5

48

14

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 3796 - qtsume

def citeste_date_intrare():

   n = int(input())
   sir = []
   for i in range(n):
       sir.append(int(input()))
   return sir

def numara_secvente_crescatoare(sir):

   numar_secvente = 0
   lungime_maxima = 1
   lungime_curenta = 1
   for i in range(1, len(sir)):
       if sir[i] >= sir[i-1]:
           lungime_curenta += 1
       else:
           if lungime_curenta > lungime_maxima:
               lungime_maxima = lungime_curenta
               numar_secvente = 1
           elif lungime_curenta == lungime_maxima:
               numar_secvente += 1
           lungime_curenta = 1
   if lungime_curenta > lungime_maxima:
       lungime_maxima = lungime_curenta
       numar_secvente = 1
   elif lungime_curenta == lungime_maxima:
       numar_secvente += 1
   return numar_secvente

def valideaza(sir, numar_secvente):

   assert len(sir) > 0
   assert numar_secvente >= 0

if __name__ == "__main__":

   sir = citeste_date_intrare()
   numar_secvente = numara_secvente_crescatoare(sir)
   valideaza(sir, numar_secvente)
   print(numar_secvente)

</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input citește datele de intrare și le returnează sub forma unei tuple ce conține n, a și queries. solve primește aceste date și calculează suma pentru fiecare interogare. Funcția validate verifică că rezultatele obținute sunt corecte. În cele din urmă, în funcția main, citim datele de intrare, apelăm funcția solve, validăm rezultatele și le afișăm.