1839 - Memory006 - Revision history

Flaviu at 20:51, 14 May 2023

2023-05-14T20:51:06Z

← Older revision		Revision as of 20:51, 14 May 2023
Line 34:		Line 34:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	~~: memory006.out~~
	~~: Datele nu corespund restricțiilor impuse~~

	== Rezolvare ==		== Rezolvare ==
Line 42:		Line 41:
	# 1839 - Memory006		# 1839 - Memory006

	def ~~count_subarrays~~(n, k, arr):		def validate_input(n, k, arr):
	~~count~~ = 0		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		prod = 1
	~~left = 0~~		for i in range(n):
			prod *= arr[i]
	for ~~right~~ in range(n):		while prod % 2 == 0:
	prod *= arr[~~right~~]		prod //= 2
			if prod == 2 ** k:
	while prod ~~> (~~2 64) / 2 k:		sequences_count += 1
	prod //= ~~arr[left]~~
	~~left += 1~~

	if prod == 2 ** k:
	~~count~~ += ~~right - left +~~ 1

	~~return count~~

	~~if __name__ == '__main__':~~		with open("memory006.out", "w") as fout:
	with open('memory006.~~in', 'r') as f_in:~~		fout.write(str(sequences_count))
	~~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~~))

			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)


Line 75:		Line 78:
	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== 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~~.		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.

	~~Î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~~.		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.

	~~Î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.		In __main__ se face citirea din fisierul de intrare "memory006.in" si se apeleaza functia calculate_sequences.

Monica Dragos: /* Date de ieșire */

2023-05-14T20:12:33Z

Date de ieșire

← Older revision		Revision as of 20:12, 14 May 2023
Line 11:		Line 11:

	Dacă datele sunt introduse corect, pe ecran se va afișa:		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."'''.		'''"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 ==

Monica Dragos: /* Date de ieșire */

2023-05-14T20:08:38Z

Date de ieșire

← Older revision		Revision as of 20:08, 14 May 2023
Line 9:		Line 9:

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire memory006.out va conține:~~
	Dacă datele sunt introduse corect, pe ecran se va afișa:		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."'''.		'''"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."'''.

Flaviu at 22:22, 13 May 2023

2023-05-13T22:22:36Z

← Older revision		Revision as of 22:22, 13 May 2023
Line 6:		Line 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 ==
			Fișierul de ieșire memory006.out va conține:
	Dacă datele sunt introduse corect, pe ecran se va afișa:		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."'''.		'''"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 ==		== Restricţii şi precizări ==
Line 24:		Line 23:
	: 7 4 2 4 5		: 7 4 2 4 5
	; Ieșire		; Ieșire
			: Datele sunt introduse correct
	: memory006.out		: memory006.out
	~~: Datele sunt introduse correct~~
	: 2		: 2

Line 31:		Line 30:
	; Intrare		; Intrare
	: memory006.in		: memory006.in
	: 5 ~~3 2 3~~		: 5 15000
	: 7 4 2 4 5		: 7 4 2 4 5
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: memory006.out		: memory006.out
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse
	~~: 1~~

	== Rezolvare ==		== Rezolvare ==
Line 43:		Line 42:
	# 1839 - Memory006		# 1839 - Memory006

	def ~~citire_date~~():		def count_subarrays(n, k, arr):
	n = ~~int(input())~~		count = 0
	v = ~~list(map(int, input~~()~~.split~~()))		prod = 1
	return ~~n, v~~		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

	~~def secvmax(n, v):~~		if __name__ == '__main__':
	st = dr = ~~st_max = dr_max = suma_max = suma = 0~~		with open('memory006.in', 'r') as f_in:
	~~for i~~ in ~~range(n~~):		n, k = map(int, f_in.readline().split())
	~~if v[i] % 2~~ =~~= 0:~~		arr = list(map(int, f_in.readline().split()))
	~~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 max(arr) > 10 ** 18 or min(arr) < 1 or k > 10000 or n > 500000:
	~~if len~~(v) != n:		print("Datele nu corespund restricțiilor impuse.")
	~~return False~~		else:
	~~for x in v~~:		print("Datele sunt introduse corect.")
	~~if x < 1 or x > 10**18:~~		print(count_subarrays(n, k, arr))
	~~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.")~~


Line 84:		Line 75:
	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== 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 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.
	~~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~~		Î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.

Flaviu at 07:46, 3 May 2023

2023-05-03T07:46:34Z

← Older revision		Revision as of 07:46, 3 May 2023
Line 8:		Line 8:
	Fișierul de intrare memory006.in conține		Fișierul de intrare memory006.in conține
	Dacă datele sunt introduse corect, pe ecran se va afișa:		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."'''.		'''"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."'''.


Line 18:		Line 18:
	* 1 ≤ k ≤ 10.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		* 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 ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: memory006.in
	: 5 3		: 5 3
	: 7 4 2 4 5		: 7 4 2 4 5
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: memory006.out
	: Datele sunt introduse correct		: Datele sunt introduse correct
	: 2		: 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 ==

Flaviu at 18:47, 27 April 2023

2023-04-27T18:47:07Z

← Older revision		Revision as of 18:47, 27 April 2023
Line 6:		Line 6:

	== Date de intrare ==		== 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~~.		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."'''.


Line 21:		Line 23:
	: 7 4 2 4 5		: 7 4 2 4 5
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct
	: 2		: 2

Line 28:		Line 32:
	# 1839 - Memory006		# 1839 - Memory006

	def ~~citeste_date_intrare~~():		def citire_date():
	~~# Citeste~~ n ~~si k~~		n = int(input())
	~~n, k~~ = map(int, input().split())		v = list(map(int, input().split()))
			return n, v

	~~# Citeste sirul de n numere~~		def secvmax(n, v):
	~~sir = list(map(int, input().split()))~~		st = dr = st_max = dr_max = suma_max = suma = 0

	~~return n, k, sir~~

	def ~~numara_secvente~~(n, ~~k, sir~~):
	~~# Initializeaza numarul de secvente cu produsul 2k la 0~~
	~~nr_secvente~~ = 0

	~~# Initializeaza produsul curent la 1~~
	~~produs = 1~~

	~~# Parcurge sirul de la stanga la dreapta~~
	for i in range(n):		for i in range(n):
	~~# Inmulteste produsul curent cu elementul curent din sir~~		if v[i] % 2 == 0:
	produs *= ~~sir~~[i]		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

	~~# Cat timp produsul este mai mare decat 2k, imparte produsul la primul element din sir~~		def validare(n, v):
	~~# si avanseaza indicele de inceput al secventei cu 1~~		if len(v) != n:
	~~while produs > (2 ** k):~~
	~~produs //= sir[i - nr_secvente]~~
	~~nr_secvente += 1~~

	~~# Daca produsul este egal cu 2k, incrementeaza numarul de secvente cu produsul 2k~~
	~~if produs == (2 ** k):~~
	~~nr_secvente += 1~~

	~~return nr_secvente~~

	def ~~valideaza_date~~(n, ~~k, sir~~):
	~~# Verifica daca n si k sunt in limitele impuse~~
	if ~~not~~ (~~1 <~~= n ~~<= 500000 and 1 <= k <= 10000)~~:
	return False		return False
			for x in v:
	~~# Verifica daca sirul contine n numere naturale nenule~~		if x < 1 or x > 10**18:
	if ~~not all(~~1 <= x <= 10**18 ~~for x in sir)~~:		return False
	return False

	return True		return True

	if __name__ == '__main__':		if __name__ == '__main__':
	~~# Citeste datele de intrare~~		n, v = citire_date()
	n, ~~k, sir~~ = ~~citeste_date_intrare~~()		if validare(n, v):
			st, dr = secvmax(n, v)
	~~# Valideaza datele de intrare~~		print("Datele sunt introduse corect.")
	if ~~not valideaza_date~~(n, k, ~~sir~~):		print(st, dr)
	print("~~Date de intrare invalide~~")
	else:		else:
	~~# Numara secventele cu produsul 2k~~		print("Datele nu corespund restricțiilor impuse.")
	~~nr_secvente = numara_secvente~~(~~n, k, sir~~)

	~~# Afiseaza numarul de secvente~~
	~~print(nr_secvente)~~

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1839/memory006 - 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 == Fișierul de ieșire memory0...

2023-04-17T20:18:44Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1839/memory006 - 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 == Fișierul de ieșire memory0...

New page

Sursa: [https://www.pbinfo.ro/probleme/1839/memory006 - 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 ==
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
: 2

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 1839 - Memory006

def citeste_date_intrare():
# Citeste n si k
n, k = map(int, input().split())

# Citeste sirul de n numere
sir = list(map(int, input().split()))

return n, k, sir

def numara_secvente(n, k, sir):
# Initializeaza numarul de secvente cu produsul 2k la 0
nr_secvente = 0

# Initializeaza produsul curent la 1
produs = 1

# Parcurge sirul de la stanga la dreapta
for i in range(n):
# Inmulteste produsul curent cu elementul curent din sir
produs *= sir[i]

# Cat timp produsul este mai mare decat 2k, imparte produsul la primul element din sir
# si avanseaza indicele de inceput al secventei cu 1
while produs > (2 ** k):
produs //= sir[i - nr_secvente]
nr_secvente += 1

# Daca produsul este egal cu 2k, incrementeaza numarul de secvente cu produsul 2k
if produs == (2 ** k):
nr_secvente += 1

return nr_secvente

def valideaza_date(n, k, sir):
# Verifica daca n si k sunt in limitele impuse
if not (1 <= n <= 500000 and 1 <= k <= 10000):
return False

# Verifica daca sirul contine n numere naturale nenule
if not all(1 <= x <= 10**18 for x in sir):
return False

return True

if __name__ == '__main__':
# Citeste datele de intrare
n, k, sir = citeste_date_intrare()

# Valideaza datele de intrare
if not valideaza_date(n, k, sir):
print("Date de intrare invalide")
else:
# Numara secventele cu produsul 2k
nr_secvente = numara_secvente(n, k, sir)

# Afiseaza numarul de secvente
print(nr_secvente)

</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