1839 - Memory006: Diferență între versiuni
Fără descriere a modificării |
Fără descriere a modificării |
||
(Nu s-au afișat 3 versiuni intermediare efectuate de alți 2 utilizatori) | |||
Linia 6: | Linia 6: | ||
== Date de intrare == | == Date de intrare == | ||
Fișierul de intrare memory006.in conține | 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 == | == Restricţii şi precizări == | ||
Linia 24: | Linia 23: | ||
: 7 4 2 4 5 | : 7 4 2 4 5 | ||
; Ieșire | ; Ieșire | ||
: Datele sunt introduse correct | |||
: memory006.out | : memory006.out | ||
: 2 | : 2 | ||
Linia 31: | Linia 30: | ||
; Intrare | ; Intrare | ||
: memory006.in | : memory006.in | ||
: 5 | : 5 15000 | ||
: 7 4 2 4 5 | : 7 4 2 4 5 | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | : Datele nu corespund restricțiilor impuse. | ||
== Rezolvare == | == Rezolvare == | ||
Linia 43: | Linia 41: | ||
# 1839 - Memory006 | # 1839 - Memory006 | ||
def | def validate_input(n, k, arr): | ||
n = | if not(1 <= n <= 500000 and 1 <= k <= 10000 and len(arr) == n): | ||
print("Datele nu corespund restricțiilor impuse.") | |||
return | 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 | def calculate_sequences(n, k, arr): | ||
if not validate_input(n, k, arr): | |||
return | |||
sequences_count = 0 | |||
prod = 1 | |||
for i in range(n): | for i in range(n): | ||
prod *= arr[i] | |||
while prod % 2 == 0: | |||
prod //= 2 | |||
if | if prod == 2 ** k: | ||
sequences_count += 1 | |||
with open("memory006.out", "w") as fout: | |||
fout.write(str(sequences_count)) | |||
if __name__ == | 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) | |||
Linia 84: | Linia 78: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
== Explicatie Rezolvare == | == 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. |
Versiunea curentă din 14 mai 2023 20:51
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.