1839 - 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

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