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 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.".
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 1
- Intrare
- memory006.in
- 5 3
- 7 4 2 4 5
- Ieșire
- memory006.out
- Datele sunt introduse correct
- 2
Exemplu 2
- Intrare
- memory006.in
- 5 3 2 3
- 7 4 2 4 5
- Ieșire
- memory006.out
- Datele nu corespund restricțiilor impuse.
- 1
Rezolvare
Rezolvare ver. 1
<syntaxhighlight lang="python" line>
- 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.")
</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