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 Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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

Datele nu corespund restricțiilor impuse.

Datele sunt introduse correct

2

Rezolvare

Rezolvare ver. 1

# 1839 - Memory006

def citire_date():
    n = int(input())
    v = list(map(int, input().split()))
    return n, v

def secvmax(n, v):
    st = dr = st_max = dr_max = suma_max = suma = 0
    for i in range(n):
        if v[i] % 2 == 0:
            suma += v[i]
            dr = i
            if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
                suma_max = suma
                st_max = st
                dr_max = dr
        else:
            suma = 0
            st = i + 1
    return st_max + 1, dr_max + 1

def validare(n, v):
    if len(v) != n:
        return False
    for x in v:
        if x < 1 or x > 10**18:
            return False
    return True

if __name__ == '__main__':
    n, v = citire_date()
    if validare(n, v):
        st, dr = secvmax(n, v)
        print("Datele sunt introduse corect.")
        print(st, dr)
    else:
        print("Datele nu corespund restricțiilor impuse.")

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