3214 - Dinamica 04 - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:27:32Z

Rezolvare

← Older revision		Revision as of 18:27, 11 January 2024
Line 21:		Line 21:
	475		475
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 123457		MOD = 123457

Mraa at 17:32, 11 January 2024

2024-01-11T17:32:35Z

← Older revision		Revision as of 17:32, 11 January 2024
Line 21:		Line 21:
	475		475
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 123457		MOD = 123457

	def numere_bune(n):		def numere_bune(n):
	~~# Inițializăm matricea dp cu 0-uri~~
	~~dp = [[0] * 2 for _ in range(n + 1)]~~

	# Pentru un singur caracter, avem 5 opțiuni (cifrele impare)		# Inițializăm matricea dp cu 0-uri
	dp[1][0] = 5		dp = [[0] * 2 for _ in range(n + 1)]
	dp[1][1] = 0		# Pentru un singur caracter, avem 5 opțiuni (cifrele impare)
			dp[1][0] = 5
			dp[1][1] = 0
			# Calculăm numărul de numere bune pentru n caractere
			for i in range(2, n + 1):
			dp[i][0] = (dp[i - 1][0] * 5 + dp[i - 1][1] * 5) % MOD
			dp[i][1] = dp[i - 1][0]
			return (dp[n][0] + dp[n][1]) % MOD

	~~# Calculăm numărul de numere bune pentru n caractere~~		if __name__ == "__main__":
	~~for i in range(2, n + 1):~~
	~~dp[i][0]~~ = ~~(dp[i - 1][0] * 5 + dp[i - 1][1] * 5) % MOD~~
	~~dp[i][1]~~ = ~~dp[i - 1][0]~~

	~~return (dp[n][0] + dp[n][1]) % MOD~~		n = int(input("Introduceți n: "))

	~~if __name__ == "__main__":~~		rezultat = numere_bune(n)
	n = int(input("Introduceți n: "))
			print(rezultat)
	rezultat = numere_bune(n)		</syntaxhighlight>

	print(rezultat)
	~~python numere_bune.py~~

Mraa: Pagină nouă: Definim un număr natural ca fiind bun dacă toate cifrele impare se află înaintea celor pare. De exemplu, numerele 13424, 400, 1357 sunt bune, pe când 34010 nu este. ==Cerința== Dându-se un număr natural nenul n, să se determine câte numere bune de n cifre există. Pentru că acest număr poate fi foarte mare, se va determina răspunsul modulo 123457. ==Date de intrare== Programul citește de la tastatură numărul n. ==Date de ieșire== Programul va afișa pe ecr...

2023-12-21T20:51:49Z

Pagină nouă: Definim un număr natural ca fiind bun dacă toate cifrele impare se află înaintea celor pare. De exemplu, numerele 13424, 400, 1357 sunt bune, pe când 34010 nu este. ==Cerința== Dându-se un număr natural nenul n, să se determine câte numere bune de n cifre există. Pentru că acest număr poate fi foarte mare, se va determina răspunsul modulo 123457. ==Date de intrare== Programul citește de la tastatură numărul n. ==Date de ieșire== Programul va afișa pe ecr...

New page

Definim un număr natural ca fiind bun dacă toate cifrele impare se află înaintea celor pare. De exemplu, numerele 13424, 400, 1357 sunt bune, pe când 34010 nu este.

==Cerința==
Dându-se un număr natural nenul n, să se determine câte numere bune de n cifre există. Pentru că acest număr poate fi foarte mare, se va determina răspunsul modulo 123457.

==Date de intrare==
Programul citește de la tastatură numărul n.

==Date de ieșire==
Programul va afișa pe ecran numărul de numere bune de n cifre, modulo 123457.

==Restricții și precizări==
Pentru 70% din punctaj, 1 ≤ n ≤ 100.000
Pentru 30% din punctaj, 100.001 ≤ n ≤ 1.000.000.000
==Exemplu==:
Intrare

3
Ieșire

475
==Rezolvare==
MOD = 123457

def numere_bune(n):
# Inițializăm matricea dp cu 0-uri
dp = [[0] * 2 for _ in range(n + 1)]

# Pentru un singur caracter, avem 5 opțiuni (cifrele impare)
dp[1][0] = 5
dp[1][1] = 0

# Calculăm numărul de numere bune pentru n caractere
for i in range(2, n + 1):
dp[i][0] = (dp[i - 1][0] * 5 + dp[i - 1][1] * 5) % MOD
dp[i][1] = dp[i - 1][0]

return (dp[n][0] + dp[n][1]) % MOD

if __name__ == "__main__":
n = int(input("Introduceți n: "))

rezultat = numere_bune(n)

print(rezultat)
python numere_bune.py