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

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

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