2239 - Pow2 - Revision history

Hotico Iulia Denisa: /* Explicatii */

2023-11-15T19:07:40Z

Explicatii

← Older revision		Revision as of 19:07, 15 November 2023
Line 107:		Line 107:
	==Explicatii==		==Explicatii==

	Cele patru perechi de indici sunt: (1,2), (1,4), (2,3), (3,4).		Cele patru perechi de indici sunt: '''(1,2), (1,4), (2,3), (3,4)'''.

Bonte Lucas Gabriel at 14:51, 12 November 2023

2023-11-12T14:51:14Z

← Older revision		Revision as of 14:51, 12 November 2023
Line 19:		Line 19:
	*Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …		*Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …

	==~~Exemplu~~==		==Exemplul 1==

	;Intrare		;Intrare

	:4		:4
	:3 5 3 13		:3 5 3 13

	;Ieșire		;Ieșire

			:Datele de intrare corespund restrictiilor impuse.
			:4

			==Exemplul 2==

			;Intrare

	:4		:4
			:a

			;Ieșire

			:Datele de intrare nu corespund restrictiilor impuse.

	==Rezolvare==		==Rezolvare==

	<syntaxhighlight lang="python" line="1" start="1">		<syntaxhighlight lang="python" line="1" start="1">

	def numar_perechi(n, a):		def verificare_restrictii(nr_n, nr_a): # functia de verificare a datelor de intrare
			if 2 <= nr_n <= 105 and all(1 <= a_i <= 109 for a_i in nr_a):
			return True
			else:
			return False


			def numar_perechi(nr_n, nr_a):
	# Generăm toate puterile lui 2 până la 2^30		# Generăm toate puterile lui 2 până la 2^30
	puteri_de_doi = [2**i for i in range(31)]		puteri_de_doi = [2**i for i in range(31)]
Line 39:		Line 61:

	# Inițializăm numărul de perechi cu 0		# Inițializăm numărul de perechi cu 0
	~~numar_perechi~~ = 0		nr_perechi = 0

	# Parcurgem fiecare element din lista a		# Parcurgem fiecare element din lista a
	for i in range(n):		for i in range(nr_n):
	# Pentru fiecare element, parcurgem lista de puteri ale lui 2		# Pentru fiecare element, parcurgem lista de puteri ale lui 2
	for putere in puteri_de_doi:		for putere in puteri_de_doi:
	# Dacă puterea lui 2 este mai mică decât numărul curent, trecem la următoarea putere		# Dacă puterea lui 2 este mai mică decât numărul curent, trecem la următoarea putere
	if putere < a[i]:		if putere < nr_a[i]:
	continue		continue

	# Calculăm numărul pe care îl căutăm în contor		# Calculăm numărul pe care îl căutăm în contor
	numar_cautat = putere - a[i]		numar_cautat = putere - nr_a[i]

	# Dacă numărul căutat este în intervalul contorului		# Dacă numărul căutat este în intervalul contorului
	if numar_cautat <= 2000000:		if numar_cautat <= 2000000:
	# Adăugăm la numărul de perechi numărul de apariții al numărului căutat		# Adăugăm la numărul de perechi numărul de apariții al numărului căutat
	~~numar_perechi~~ += contor[numar_cautat]		nr_perechi += contor[numar_cautat]

	# Dacă numărul curent este în intervalul contorului		# Dacă numărul curent este în intervalul contorului
	if a[i] <= 2000000:		if nr_a[i] <= 2000000:
	# Incrementăm contorul pentru numărul curent		# Incrementăm contorul pentru numărul curent
	contor[a[i]] += 1		contor[nr_a[i]] += 1

			return nr_perechi

	~~return numar_perechi~~

	~~# Citim datele de intrare~~		if __name__ == '__main__':
	n = int(input())		try:
	a = list(map(int, input().split()))		n = int(input("Introduceti numarul n: ")) # citirea numarului de linii si coloane
			a = list(map(int, input().split()))

	# ~~Apelăm funcția și afișăm rezultatul~~		if verificare_restrictii(n, a): # verificam datele de intrare
	print(numar_perechi(n, a))		print("Datele de intrare corespund restrictiilor impuse.")
			print(numar_perechi(n, a)) # apelam functia de rezolvare
			else:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			# ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
			except ValueError:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			except IndexError:
			print("Datele de intrare nu corespund restrictiilor impuse.")

	</syntaxhighlight>		</syntaxhighlight>

Bonte Lucas Gabriel: Pagină nouă: Se consideră un șir '''a[1]''', '''a[2]''',…, '''a[n]''' de numere naturale nenule. ==Cerință== Să se determine câte perechi de indici '''(i, j), 1 ≤ i < j ≤ n''', există cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui 2. ==Date de intrare== Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale nenule, separate prin spații. ==Date de ieșire== Programul va afișa pe ecran un singur număr natur...

2023-10-24T21:42:10Z

Pagină nouă: Se consideră un șir '''a[1]''', '''a[2]''',…, '''a[n]''' de numere naturale nenule. ==Cerință== Să se determine câte perechi de indici '''(i, j), 1 ≤ i < j ≤ n''', există cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui 2. ==Date de intrare== Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale nenule, separate prin spații. ==Date de ieșire== Programul va afișa pe ecran un singur număr natur...

New page

Se consideră un șir '''a[1]''', '''a[2]''',…, '''a[n]''' de numere naturale nenule.

==Cerință==

Să se determine câte perechi de indici '''(i, j), 1 ≤ i < j ≤ n''', există cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui 2.

==Date de intrare==

Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale nenule, separate prin spații.

==Date de ieșire==

Programul va afișa pe ecran un singur număr natural reprezentând numărul de perechi de indici distincți '''(i, j)''' cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui 2.

==Restricții și precizări==

*'''2 ≤ n ≤ 100.000'''
*'''1 ≤ a[i] ≤ 1.000.000.000''', pentru orice '''i = 1..n'''
*Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …

==Exemplu==

;Intrare
:4
:3 5 3 13

;Ieșire
:4

==Rezolvare==
<syntaxhighlight lang="python" line="1" start="1">

def numar_perechi(n, a):
# Generăm toate puterile lui 2 până la 2^30
puteri_de_doi = [2**i for i in range(31)]

# Inițializăm un contor pentru fiecare număr posibil din șir
contor = [0]*2000001

# Inițializăm numărul de perechi cu 0
numar_perechi = 0

# Parcurgem fiecare element din lista a
for i in range(n):
# Pentru fiecare element, parcurgem lista de puteri ale lui 2
for putere in puteri_de_doi:
# Dacă puterea lui 2 este mai mică decât numărul curent, trecem la următoarea putere
if putere < a[i]:
continue

# Calculăm numărul pe care îl căutăm în contor
numar_cautat = putere - a[i]

# Dacă numărul căutat este în intervalul contorului
if numar_cautat <= 2000000:
# Adăugăm la numărul de perechi numărul de apariții al numărului căutat
numar_perechi += contor[numar_cautat]

# Dacă numărul curent este în intervalul contorului
if a[i] <= 2000000:
# Incrementăm contorul pentru numărul curent
contor[a[i]] += 1

return numar_perechi

# Citim datele de intrare
n = int(input())
a = list(map(int, input().split()))

# Apelăm funcția și afișăm rezultatul
print(numar_perechi(n, a))

</syntaxhighlight>

==Explicatii==

Cele patru perechi de indici sunt: (1,2), (1,4), (2,3), (3,4).