3821 - Magic Digits - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:32:59Z

Rezolvare

← Older revision		Revision as of 18:32, 11 January 2024
Line 34:		Line 34:
	sunt : 132 , 152 , 512.		sunt : 132 , 152 , 512.
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 666013		MOD = 666013

Mraa at 17:39, 11 January 2024

2024-01-11T17:39:47Z

← Older revision		Revision as of 17:39, 11 January 2024
Line 34:		Line 34:
	sunt : 132 , 152 , 512.		sunt : 132 , 152 , 512.
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 666013		MOD = 666013

	def numere_grad_frumusete(N, k):		def numere_grad_frumusete(N, k):
	~~# Funcție auxiliară pentru calculul coeficientului binomial~~
	~~def comb(n, r):~~
	~~result = 1~~
	~~for i in range(r):~~
	~~result = (result * (n - i)) % MOD~~
	~~result = (result * pow(i + 1, MOD - 2, MOD)) % MOD~~
	~~return result~~

	# Funcție recursivă pentru generarea numărului de aranjamente		# Funcție auxiliară pentru calculul coeficientului binomial
	def count_arrangements(digit_counts, current_k):		def comb(n, r):
	if current_k < 0:		result = 1
	return 0		for i in range(r):
	if current_k == 0:		result = (result * (n - i)) % MOD
	# Calculăm numărul de moduri în care putem aranja cifrele		result = (result * pow(i + 1, MOD - 2, MOD)) % MOD
	result = 1		return result
	for count in digit_counts:		# Funcție recursivă pentru generarea numărului de aranjamente
	result = (result * comb(N, count)) % MOD		def count_arrangements(digit_counts, current_k):
	return result		if current_k < 0:
			return 0
	total_arrangements = 0		if current_k == 0:
	for i in range(1, 10):		# Calculăm numărul de moduri în care putem aranja cifrele
	# Adăugăm cifra i și continuăm recursiv		result = 1
	new_digit_counts = digit_counts[:]		for count in digit_counts:
	new_digit_counts.append(i)		result = (result * comb(N, count)) % MOD
	total_arrangements = (total_arrangements + count_arrangements(new_digit_counts, current_k - 1)) % MOD		return result
			total_arrangements = 0
	return total_arrangements		for i in range(1, 10):
			# Adăugăm cifra i și continuăm recursiv
	return count_arrangements([], k)		new_digit_counts = digit_counts[:]
			new_digit_counts.append(i)
			total_arrangements = (total_arrangements + count_arrangements(new_digit_counts, current_k - 1)) % MOD
			return total_arrangements
			return count_arrangements([], k)

	if __name__ == "__main__":		if __name__ == "__main__":
	~~# Citim datele de intrare~~
	~~N, k = map(int, input().split())~~

	# Calculăm rezultatul și afișăm rezultatul modulo MOD		# Citim datele de intrare
	rezultat = numere_grad_frumusete(N, k)		N, k = map(int, input().split())
	print(rezultat)		# Calculăm rezultatul și afișăm rezultatul modulo MOD
	~~python grad_frumusete.py~~		rezultat = numere_grad_frumusete(N, k)
			print(rezultat)
			</syntaxhighlight>

Mraa: Pagină nouă: ==Cerința== Le Quack , mare fan al Lord Of The Rings , dar și al vrăjitoriei , află de la Gandalf că cifrele magice sunt { 1,2,3,4,5,6,7,8,9 } , cifra 0 este prea asemănătoare cu ochiul lui Sauron , fiind astfel considerată malefica. Le Quack iubeste aceste cifre magice încât le-a studiat mai atent și a observat că acestea pot forma numere de diferite lungimi ( ex : 1124 , 312 , 91235 ). Pentru fiecare număr format cu cifre magice definim gradul de frumusete ca f...

2023-12-21T21:21:19Z

Pagină nouă: ==Cerința== Le Quack , mare fan al Lord Of The Rings , dar și al vrăjitoriei , află de la Gandalf că cifrele magice sunt { 1,2,3,4,5,6,7,8,9 } , cifra 0 este prea asemănătoare cu ochiul lui Sauron , fiind astfel considerată malefica. Le Quack iubeste aceste cifre magice încât le-a studiat mai atent și a observat că acestea pot forma numere de diferite lungimi ( ex : 1124 , 312 , 91235 ). Pentru fiecare număr format cu cifre magice definim gradul de frumusete ca f...

New page

==Cerința==
Le Quack , mare fan al Lord Of The Rings , dar și al vrăjitoriei , află de la Gandalf că cifrele magice sunt { 1,2,3,4,5,6,7,8,9 } , cifra 0 este prea asemănătoare cu ochiul lui Sauron , fiind astfel considerată malefica. Le Quack iubeste aceste cifre magice încât le-a studiat mai atent și a observat că acestea pot forma numere de diferite lungimi ( ex : 1124 , 312 , 91235 ). Pentru fiecare număr format cu cifre magice definim gradul de frumusete ca fiind suma dintre frecvența minima a unei cifre magice și frecvența maxima a unei cifre magice care se găsește în număr. Formal , dacă construim un vector f , unde f[i] este numărul de apariții ale cifrei i și se șterg toate valorile pentru care f[i] = 0 , atunci min(f) + max(f) = k , unde k este gradul de frumusețe al numărului. De exemplu , pentru numărul 131 gradul de frumusețe este 1+2 = 3. Le Quack își pune următoarea întrebare : Câte numere de n cifre au gradul de frumusețe egal cu k ?

==Date de intrare==
Programul citește de la tastatură pe prima linie un număr N reprezentând lungimea numerelor care trebuie numărate și k , gradul de frumusețe al lor.

==Date de ieșire==
Programul va afișa pe ecran numărul cerut modulo 666013.

==Restricții și precizări==
N <= 300.
K <= 2*N.
Pentru 10 puncte N <= 6.
Pentru alte 10 puncte , K > N.
Pentru restul de 80 de puncte , K <= N , N > 6 si N <= 300.
Nu uitați că cifra 0 nu poate fi folosită !
==Exemplu==:
Intrare

2 2
Ieșire

72
Intrare

3 2
Ieșire

504
==Explicație==
În primul exemplu , sunt 72 de numere de lungime 2 cu gradul de frumusețe 2. câteva dintre acestea
sunt : 13 , 14 , 32.
În al doilea exemplu sunt 504 numere de lungime 3 cu gradul de frumusețe 2. Câteva dintre acestea
sunt : 132 , 152 , 512.
==Rezolvare==
MOD = 666013

def numere_grad_frumusete(N, k):
# Funcție auxiliară pentru calculul coeficientului binomial
def comb(n, r):
result = 1
for i in range(r):
result = (result * (n - i)) % MOD
result = (result * pow(i + 1, MOD - 2, MOD)) % MOD
return result

# Funcție recursivă pentru generarea numărului de aranjamente
def count_arrangements(digit_counts, current_k):
if current_k < 0:
return 0
if current_k == 0:
# Calculăm numărul de moduri în care putem aranja cifrele
result = 1
for count in digit_counts:
result = (result * comb(N, count)) % MOD
return result

total_arrangements = 0
for i in range(1, 10):
# Adăugăm cifra i și continuăm recursiv
new_digit_counts = digit_counts[:]
new_digit_counts.append(i)
total_arrangements = (total_arrangements + count_arrangements(new_digit_counts, current_k - 1)) % MOD

return total_arrangements

return count_arrangements([], k)

if __name__ == "__main__":
# Citim datele de intrare
N, k = map(int, input().split())

# Calculăm rezultatul și afișăm rezultatul modulo MOD
rezultat = numere_grad_frumusete(N, k)
print(rezultat)
python grad_frumusete.py