Editing 1839 - Memory006

Sursa: [https://www.pbinfo.ro/probleme/1839/memory006 - Memory006]
----
== Cerinţa ==
Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2k, unde k este un număr natural dat.


== Date de intrare ==
Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații.


== Date de ieșire == 
Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 500.000
* 1 ≤ k ≤ 10.000
* numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 10^18
== Exemplu ==
; Intrare
: 5 3
: 7 4 2 4 5
; Ieșire
: 2

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 1839 - Memory006

def citeste_date_intrare():
    # Citeste n si k
    n, k = map(int, input().split())

    # Citeste sirul de n numere
    sir = list(map(int, input().split()))

    return n, k, sir

def numara_secvente(n, k, sir):
    # Initializeaza numarul de secvente cu produsul 2k la 0
    nr_secvente = 0

    # Initializeaza produsul curent la 1
    produs = 1

    # Parcurge sirul de la stanga la dreapta
    for i in range(n):
        # Inmulteste produsul curent cu elementul curent din sir
        produs *= sir[i]

        # Cat timp produsul este mai mare decat 2k, imparte produsul la primul element din sir
        # si avanseaza indicele de inceput al secventei cu 1
        while produs > (2 ** k):
            produs //= sir[i - nr_secvente]
            nr_secvente += 1

        # Daca produsul este egal cu 2k, incrementeaza numarul de secvente cu produsul 2k
        if produs == (2 ** k):
            nr_secvente += 1

    return nr_secvente

def valideaza_date(n, k, sir):
    # Verifica daca n si k sunt in limitele impuse
    if not (1 <= n <= 500000 and 1 <= k <= 10000):
        return False

    # Verifica daca sirul contine n numere naturale nenule
    if not all(1 <= x <= 10**18 for x in sir):
        return False

    return True

if __name__ == '__main__':
    # Citeste datele de intrare
    n, k, sir = citeste_date_intrare()

    # Valideaza datele de intrare
    if not valideaza_date(n, k, sir):
        print("Date de intrare invalide")
    else:
        # Numara secventele cu produsul 2k
        nr_secvente = numara_secvente(n, k, sir)

        # Afiseaza numarul de secvente
        print(nr_secvente)


</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția citeste_date_intrare citește numerele n și k de pe prima linie a fișierului de intrare, apoi citește sirul de n numere de pe a doua linie și le returnează sub formă de tuplu (n, k, sir).
Funcția numara_secvente primește numerele n, k și sirul sir și returnează numărul de secvențe ale sir care au produsul egal cu 2 ** k.
Pentru a număra secvențele cu produsul egal cu 2 ** k, vom parcurge sirul de la stânga la dreapta și vom menține un produs curent inițial egal cu 1 și un număr de secvențe inițial egal cu 0. La fiecare pas, vom înmulți produsul curent