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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi fișierul memory006.out va conține numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k., 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 ≤ 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 1

Intrare: memory006.in; 5 3; 7 4 2 4 5
Ieșire: Datele sunt introduse correct; memory006.out; 2

Exemplu 2

Intrare: memory006.in; 5 15000; 7 4 2 4 5
Ieșire: Datele nu corespund restricțiilor impuse.; memory006.out; Datele nu corespund restricțiilor impuse

Rezolvare

Rezolvare ver. 1

1839 - Memory006

def count_subarrays(n, k, arr):

   count = 0
   prod = 1
   left = 0
   
   for right in range(n):
       prod *= arr[right]
       
       while prod > (2 ** 64) / 2 ** k:
           prod //= arr[left]
           left += 1
       
       if prod == 2 ** k:
           count += right - left + 1
   
   return count

if __name__ == '__main__':

   with open('memory006.in', 'r') as f_in:
       n, k = map(int, f_in.readline().split())
       arr = list(map(int, f_in.readline().split()))

   if max(arr) > 10 ** 18 or min(arr) < 1 or k > 10000 or n > 500000:
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       print(count_subarrays(n, k, arr))

</syntaxhighlight>

Explicatie Rezolvare

Funcția count_subarrays primește ca argumente lungimea șirului n, numărul natural k și șirul de numere naturale nenule arr. Returnează numărul de subșiruri ale șirului arr care au produsul elementelor egal cu 2^k.

În cadrul funcției, inițializăm count la 0, prod la 1 și left la 0. Parcurgem șirul arr cu un indice right și actualizăm prod înmulțind cu fiecare element arr[right]. În timp ce prod depășește o anumită valoare calculată cu ajutorul lui k, actualizăm prod împărțind cu elementele de la începutul subșirului până când prod este mai mic sau egal cu acea valoare.

Dacă prod este egal cu 2^k, incrementăm count cu numărul de elemente din subșirul curent.

În funcția main, citim datele de intrare din fișierul memory006.in și verificăm dacă acestea corespund restricțiilor impuse în enunțul problemei. Dacă datele sunt valide, apelăm funcția count_subarrays și afișăm rezultatul. Dacă datele nu sunt valide, afișăm un mesaj corespunzător.