Editing 3796 - qtsume

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