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

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.