Editing 4233 - SecvDeSumaS

Sursa: [https://www.pbinfo.ro/probleme/4233/secvdesumas 4233 - SecvDeSumaS]
----
== Cerinţa ==
Se dă un șir a1, a2, …, an de numere întregi și un număr întreg S. Să se determine numărul secvențelor nevide care au suma egală cu S.


== Date de intrare ==
Programul citește de la tastatură de pe prima linie numerele n, S, iar de pe a doua linie numerele separate prin spații a1, a2, …, an.


== Date de ieșire == 
Programul va afișa pe ecran numărul numărul secvențelor nevide care au suma egală cu S.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1.000.000
* -1000 ≤ ai ≤ 1000 pentru orice i=1..n
* -1.000.000.000 ≤ S ≤ 1.000.000.000
O secvență nevidă este formată din unul sau mai multe elemente ale șirului aflate pe poziții consecutive.nță cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător
== Exemplu ==
; Intrare
: 13 -10
: 2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17
; Ieșire
: 4

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 4233 - SecvDeSumaS

def read_input():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    return n, s, a

def count_subarrays(n, s, a):
    sum_count = {0: 1}
    current_sum = 0
    subarrays = 0
    for i in range(n):
        current_sum += a[i]
        if current_sum - s in sum_count:
            subarrays += sum_count[current_sum - s]
        if current_sum in sum_count:
            sum_count[current_sum] += 1
        else:
            sum_count[current_sum] = 1
    return subarrays

def validate_input(n, s, a):
    assert 1 <= n <= 1000000
    assert -1000 <= s <= 1000
    assert -1000 <= min(a) and max(a) <= 1000

if __name__ == '__main__':
    n, s, a = read_input()
    validate_input(n, s, a)
    print(count_subarrays(n, s, a))


</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare de la tastatură și le returnează într-o tuplă.
Funcția count_subarrays primește numărul n, suma s și vectorul a și returnează numărul de subșiruri (secvențe) cu suma egală cu s. Aceasta utilizează o metodă eficientă de calculare a numărului de subșiruri cu o anumită sumă, care se bazează pe utilizarea unui dicționar sum_count care stochează numărul de subșiruri cu suma curentă. Inițial, acest dicționar conține o singură valoare, anume 0, cu numărul de apariții 1, pentru că înainte de a începe să adunăm elementele din vector, suma este 0. Pe măsură ce iterăm prin elementele vectorului, actualizăm suma curentă și verificăm dacă diferența dintre suma curentă și s a mai apărut în vectorul a. Dacă da, atunci adăugăm numărul de subșiruri care au suma egală cu diferența respectivă. În plus, adăugăm și numărul de apariții curent al sumei în dicționarul sum_count. Dacă suma curentă a mai fost întâlnită, atunci incrementăm numărul de apariții al acesteia în dicționar, altfel adăugăm o intrare nouă cu numărul de apariții 1.
Funcția validate_input validează datele de intrare conform restricțiilor din enunț.
În blocul if __name__ == '__main__': se apelează funcțiile în ordinea necesară și se afișează rezultatul.