3295 - Perm Euler - Revision history

Alexandra Leș at 17:29, 11 April 2023

2023-04-11T17:29:18Z

← Older revision		Revision as of 17:29, 11 April 2023
Line 6:		Line 6:
	Fișierul de intrare '''permeuler.in''' conține pe prima linie cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000''', separate prin spații.		Fișierul de intrare '''permeuler.in''' conține pe prima linie cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000''', separate prin spații.
	== Date de ieşire ==		== Date de ieşire ==
	~~Fișierul~~ de ieșire '''permeuler.out''' va conține ~~pe prima linie~~ primul număr '''x''' pentru care '''φ(x)''' e o permutare a lui '''x''' și fracția '''x/φ(x)''' are valoare minimă.		Dacă datele sunt introduse corect, în fișier se va afișa:'''"Datele sunt introduse corect."''', apoi pe un rând nou fișierul de ieșire '''permeuler.out''' va conține primul număr '''x''' pentru care '''φ(x)''' e o permutare a lui '''x''' și fracția '''x/φ(x)''' are valoare minimă. În cazul în care datele nu respectă restricțiile, se va afișa în fișier:'''"Datele nu corespund restricțiilor impuse."'''.
	== Restricții și precizări ==		== Restricții și precizări ==
	* în fișier sunt cel mult 10000 de numere		* în fișier sunt cel mult 10000 de numere
Line 14:		Line 14:
	: 1000 345 21 34567 5678 63 345678 1234		: 1000 345 21 34567 5678 63 345678 1234
	; permeuler.out		; permeuler.out
	: Datele introduse ~~corespund restricțiilor impuse~~.		:Datele sunt introduse corect.
	: 21		: 21
	== Explicație ==		== Explicație ==
Line 20:		Line 20:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
			#Funția de verificare a datelor de intrare
			def validare_date(numere):
			if len(numere) > 10000:
			return False
			if not all(0 < n < 10000000 for n in numere):
			return False
			if len(set(numere)) != len(numere):
			return False
			return True
			#Funcția calculează indicatorul lui Euler pentru n
	def phi(n):		def phi(n):
	~~result~~ = n		rezultat = n
	i = 2		i = 2

	while i*i <= n:		while i * i <= n:
	if n % i == 0:		if n % i == 0:
	while n % i == 0:		while n % i == 0:
	n //= i		n //= i
	~~result~~ -= ~~result~~ // i		rezultat -= rezultat // i
	i += 1		i += 1

	if n > 1:		if n > 1:
	~~result~~ -= ~~result~~ // n		rezultat -= rezultat // n

	~~return result~~

			return rezultat

	def ~~is_permutation~~(a, b):		#Funcția verifică dacă numerele a este o permutare a lui b și invers
			def este_permutare(a, b):
	dict_a = {c: str(a).count(str(c)) for c in range(10)}		dict_a = {c: str(a).count(str(c)) for c in range(10)}
	dict_b = {c: str(b).count(str(c)) for c in range(10)}		dict_b = {c: str(b).count(str(c)) for c in range(10)}
Line 45:		Line 55:
	if __name__ == '__main__':		if __name__ == '__main__':
	with open('permeuler.in', 'r') as f:		with open('permeuler.in', 'r') as f:
	~~nums~~ = list(map(int, f.readline().split()))		numere = list(map(int, f.readline().split()))

	~~min_ratio~~ = float('inf')		# Verificăm dacă datele de intrare sunt valide
	~~result~~ = 0		if not validare_date(numere):
			f.write("Datele introduse nu corespund restrictiilor impuse.")
	for n in ~~nums~~:		exit(1)

			minimul_raportului = float('inf')
			rezultat = 0
			# Parcurgem fiecare număr din lista și calculăm indicatorul Euler pentru acesta
			for n in numere:
	phin = phi(n)		phin = phi(n)
	~~ratio~~ = n / phin		raport = n / phin
			# Verifică dacă n și indicator_n sunt permutări una a celeilalte și dacă raportul este minim
	if ~~is_permutation~~(n, phin) and ~~ratio~~ < ~~min_ratio~~:		if este_permutare(n, phin) and raport < minimul_raportului:
	~~min_ratio~~ = ~~ratio~~		minimul_raportului = raport
	~~result~~ = n		rezultat = n
			#Deschidem fișierul și afișăm mesajul de confirmare si rezultatul
	with open('permeuler.out', 'w') as f:		with open('permeuler.out', 'w') as f:
	f.write(str(~~result~~))		f.write("Datele sunt introduse corect.\n")
			f.write(str(rezultat))


	</syntaxhighlight>		</syntaxhighlight>

Alexandra Leș: /* Rezolvare */

2023-03-18T19:29:31Z

Rezolvare

← Older revision		Revision as of 19:29, 18 March 2023
Line 20:		Line 20:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	~~def validare_date_numere(n):~~
	~~flag = False~~
	~~if 0 <= int(n) <= 1000:~~
	~~flag = True~~
	~~return flag~~

	def phi(n):		def phi(n):
	result = n		result = n
Line 41:		Line 35:

	return result		return result


	def is_permutation(a, b):		def is_permutation(a, b):
Line 46:		Line 41:
	dict_b = {c: str(b).count(str(c)) for c in range(10)}		dict_b = {c: str(b).count(str(c)) for c in range(10)}
	return dict_a == dict_b		return dict_a == dict_b


	if __name__ == '__main__':		if __name__ == '__main__':
	~~if validare_date_numere(n):~~
	~~print("\nDatele de intrare corespund restricțiilor impuse.\n")~~
	with open('permeuler.in', 'r') as f:		with open('permeuler.in', 'r') as f:
	nums = list(map(int, f.readline().split()))		nums = list(map(int, f.readline().split()))
Line 66:		Line 60:
	with open('permeuler.out', 'w') as f:		with open('permeuler.out', 'w') as f:
	f.write(str(result))		f.write(str(result))
	~~else:~~
	~~print("Datele de intrare nu corespund restricțiilor impuse.")~~




	</syntaxhighlight>		</syntaxhighlight>

Alexandra Leș: Pagină nouă: == Cerinţa == Indicatorul lui Euler, '''φ(n)''' – câteodată numit funcția phi, e folosit pentru a determina câte numere pozitive mai mici decât '''n''' care sunt relativ prime cu '''n''' există. De exemplu, cum '''1''', '''2''','''4''', '''5''', '''7''' și '''8''' sunt toate mai mici decât '''9''' și sunt relativ prime la '''9''', '''φ(9)=6'''. Numărul '''1''' e considerat a fi relativ prim cu toate numerele naturale, deci '''φ(1)=1'''. În mod interesant, '''...

2023-03-17T19:42:12Z

Pagină nouă: == Cerinţa == Indicatorul lui Euler, '''φ(n)''' – câteodată numit funcția phi, e folosit pentru a determina câte numere pozitive mai mici decât '''n''' care sunt relativ prime cu '''n''' există. De exemplu, cum '''1''', '''2''','''4''', '''5''', '''7''' și '''8''' sunt toate mai mici decât '''9''' și sunt relativ prime la '''9''', '''φ(9)=6'''. Numărul '''1''' e considerat a fi relativ prim cu toate numerele naturale, deci '''φ(1)=1'''. În mod interesant, '''...

New page

== Cerinţa ==
Indicatorul lui Euler, '''φ(n)''' – câteodată numit funcția phi, e folosit pentru a determina câte numere pozitive mai mici decât '''n''' care sunt relativ prime cu '''n''' există. De exemplu, cum '''1''', '''2''','''4''', '''5''', '''7''' și '''8''' sunt toate mai mici decât '''9''' și sunt relativ prime la '''9''', '''φ(9)=6'''. Numărul '''1''' e considerat a fi relativ prim cu toate numerele naturale, deci '''φ(1)=1'''. În mod interesant, '''φ(87109)=79180''', și se poate observa că '''87109''' e o permutare a lui '''79180'''.

Se consideră un șir de cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000'''. Să se scrie un program care găsește valoarea lui '''n''', pentru care '''φ(n)''' e o permutare a lui n și fracția '''n/φ(n)''' are valoare minimă. Dacă sunt mai multe valori cu aceeași proprietate atunci se scrie prima valoare din șir. Dacă nu sunt valori cu proprietatea menționată se va scrie valoarea '''0'''.
== Date de intrare ==
Fișierul de intrare '''permeuler.in''' conține pe prima linie cel mult '''10000''' de numere naturale distincte mai mici decât '''10.000.000''', separate prin spații.
== Date de ieşire ==
Fișierul de ieșire '''permeuler.out''' va conține pe prima linie primul număr '''x''' pentru care '''φ(x)''' e o permutare a lui '''x''' și fracția '''x/φ(x)''' are valoare minimă.
== Restricții și precizări ==
* în fișier sunt cel mult 10000 de numere
* numerele de pe prima linie a fișierului de intrare vor fi mai mici decât 10.000.000
== Exemplu ==
; permeuler.in
: 1000 345 21 34567 5678 63 345678 1234
; permeuler.out
: Datele introduse corespund restricțiilor impuse.
: 21
== Explicație ==
În fișierul de intrare sunt '''2''' numere care îndeplinesc proprietatea cerută de problemă: '''21''' care are '''φ(21)=12''' și raportul '''21/φ(21)=1.75''' și '''63''' care are '''φ(63)=36''' și raportul '''63/φ(63)=1.75'''. În fișierul de ieșire va fi scrisă valoarea '''21'''.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def validare_date_numere(n):
flag = False
if 0 <= int(n) <= 1000:
flag = True
return flag

def phi(n):
result = n
i = 2

while i*i <= n:
if n % i == 0:
while n % i == 0:
n //= i
result -= result // i
i += 1

if n > 1:
result -= result // n

return result

def is_permutation(a, b):
dict_a = {c: str(a).count(str(c)) for c in range(10)}
dict_b = {c: str(b).count(str(c)) for c in range(10)}
return dict_a == dict_b

if __name__ == '__main__':
if validare_date_numere(n):
print("\nDatele de intrare corespund restricțiilor impuse.\n")
with open('permeuler.in', 'r') as f:
nums = list(map(int, f.readline().split()))

min_ratio = float('inf')
result = 0

for n in nums:
phin = phi(n)
ratio = n / phin

if is_permutation(n, phin) and ratio < min_ratio:
min_ratio = ratio
result = n

with open('permeuler.out', 'w') as f:
f.write(str(result))
else:
print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>