4233 - SecvDeSumaS
Sursa: 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
<syntaxhighlight lang="python" line>
- 4233 - SecvDeSumaS
def validate_input(n, S, arr):
if not (1 <= n <= 1000000):
return False
if len(arr) != n:
return False
if any(num < -1000 or num > 1000 for num in arr):
return False
if not (-1000000000 <= S <= 1000000000):
return False
return True
def count_sequences(n, S, arr):
if not validate_input(n, S, arr):
return "Datele nu corespund restricțiilor impuse."
count = 0
current_sum = 0
prefix_sum = {0: 1}
for i in range(n):
current_sum += arr[i]
diff = current_sum - S
if diff in prefix_sum:
count += prefix_sum[diff]
prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
return count
if __name__ == '__main__':
n, S = map(int, input("Introduceti n si S: ").split())
arr = list(map(int, input("Introduceti vectorul de numere întregi: ").split()))
result = count_sequences(n, S, arr) print(result)
</syntaxhighlight>
Explicatie Rezolvare
Funcția validate_input(n, S, arr) este responsabilă pentru validarea datelor de intrare. Aceasta verifică dacă valorile îndeplinesc restricțiile impuse în cerință. Verifică următoarele condiții:
n trebuie să fie între 1 și 1.000.000 lungimea listei arr trebuie să fie n fiecare element din arr trebuie să fie între -1000 și 1000 S trebuie să fie între -1.000.000.000 și 1.000.000.000 Dacă oricare dintre aceste condiții nu este îndeplinită, funcția returnează False, altfel returnează True. Funcția count_sequences(n, S, arr) primește parametrii validați și calculează numărul de secvențe nevide care au suma egală cu S.
Verifică dacă datele de intrare sunt valide folosind funcția validate_input(). Dacă nu sunt valide, returnează mesajul "Datele nu corespund restricțiilor impuse." Inițializează variabila count cu 0 pentru a număra secvențele care îndeplinesc condiția. Inițializează variabilele current_sum cu 0 și prefix_sum ca un dicționar cu o singură valoare inițială: {0: 1}. Aceasta înseamnă că avem o sumă curentă de 0 și avem o secvență goală cu sumă 0 (aceasta va fi folosită pentru a număra secvențele care încep de la începutul listei arr și au suma S). Parcurge fiecare element num din arr. Adaugă num la current_sum. Calculează diferența diff dintre current_sum și S. Verifică dacă diff există în dicționarul prefix_sum. Dacă există, înseamnă că am găsit o secvență cu suma S. Adaugă valoarea corespunzătoare din prefix_sum la count. Incrementăm sau actualizăm valoarea corespunzătoare current_sum în dicționarul prefix_sum. La sfârșitul buclei, count va conține numărul total de secvențe care au suma S. Returnează valoarea count. Blocul if __name__ == '__main__': este responsabil pentru citirea datelor de intrare și apelarea funcțiilor corespunzătoare.
Citim n și S de la tastatură și le convertim la întregi utilizând map și int. Citim vectorul arr de numere întregi de la tastatură, îl splituim într-o listă folosind split