3796 - qtsume: Diferență între versiuni
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3796/qtsume 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 fi...) |
(Nicio diferență)
|
Versiunea de la data 17 aprilie 2023 20:30
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
# 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)
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.