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

Dacă datele sunt introduse corect, pe ecran se va afișa: '"Datele sunt introduse corect.", apoi pe un rând nou numărul numărul secvențelor nevide care au suma egală cu S, 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 ≤ 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 1

Intrare: 13 -10; 2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17
Ieșire: Datele sunt introduse correct.; 4

Exemplu

Intrare: 22 3 5 9 2; 1 2 3 5 0 0 -1 0 2 -76 23
Ieșire: Datele nu corespund restricțiilor impuse.

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):

   if not (1 <= n <= 1000000):
       return False
   if not (-1000 <= s <= 1000):
       return False
   if not (-1000 <= min(a) and max(a) <= 1000):
       return False
   return True

if __name__ == '__main__':

   n, s, a = read_input()
   if validate_input(n, s, a):
       print("Datele sunt introduse corect.")
       print(count_subarrays(n, s, a))
   else:
       print("Datele nu corespund restricțiilor impuse.")

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