1839 - Memory006

Sursa: - 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.

Rezolvare

Rezolvare ver. 1

# 1839 - Memory006

def validate_input(n, k, arr):
    if not(1 <= n <= 500000 and 1 <= k <= 10000 and len(arr) == n):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    for num in arr:
        if not(1 <= num <= 10**18):
            print("Datele nu corespund restricțiilor impuse.")
            return False
    print("Datele sunt introduse corect.")
    return True

def calculate_sequences(n, k, arr):
    if not validate_input(n, k, arr):
        return

    sequences_count = 0
    prod = 1
    for i in range(n):
        prod *= arr[i]
        while prod % 2 == 0:
            prod //= 2
            if prod == 2 ** k:
                sequences_count += 1

    with open("memory006.out", "w") as fout:
        fout.write(str(sequences_count))

if __name__ == "__main__":
    with open("memory006.in", "r") as fin:
        n, k = map(int, fin.readline().split())
        arr = list(map(int, fin.readline().split()))
    calculate_sequences(n, k, arr)

Explicatie Rezolvare

Functia validate_input verifica daca datele de intrare sunt valide, in functie de restrictiile impuse. Daca toate valorile sunt valide, functia returneaza True, altfel returneaza False si afiseaza un mesaj de eroare.

Functia calculate_sequences primeste ca parametri n - numarul de elemente din sir, k - numarul dat si arr - sirul de numere date. Daca datele de intrare sunt valide, functia calculeaza numarul de secvente din sir care au produsul elementelor egal cu 2^k si il scrie in fisierul de iesire "memory006.out". Algoritmul este de a parcurge sirul si de a calcula produsul elementelor din secvente succesive, impartind la 2 pana cand produsul devine egal cu 2^k. Cand acest lucru se intampla, numarul de secvente creste cu 1.

In __main__ se face citirea din fisierul de intrare "memory006.in" si se apeleaza functia calculate_sequences.