3990 - Dinamica 09 - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:25:21Z

Rezolvare

← Older revision		Revision as of 18:25, 11 January 2024
Line 21:		Line 21:
	Numerele sunt 12, 14, 24, 32, 34, 42.		Numerele sunt 12, 14, 24, 32, 34, 42.
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	def count_numbers(n):		def count_numbers(n):

Mraa at 17:28, 11 January 2024

2024-01-11T17:28:07Z

← Older revision		Revision as of 17:28, 11 January 2024
Line 21:		Line 21:
	Numerele sunt 12, 14, 24, 32, 34, 42.		Numerele sunt 12, 14, 24, 32, 34, 42.
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	def count_numbers(n):		def count_numbers(n):
	~~mod = 123457~~

	# Inițializare vector dp		mod = 123457
	dp = [[0] * 4 for _ in range(n + 1)]		# Inițializare vector dp
	for i in range(1, 4):		dp = [[0] * 4 for _ in range(n + 1)]
	dp[1][i] = 1		for i in range(1, 4):
			dp[1][i] = 1
			# Calcul numărul de numere
			for i in range(2, n + 1):
			dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod
			dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod
			dp[i][3] = (dp[i - 1][1] + dp[i - 1][2]) % mod
			result = (dp[n][1] + dp[n][2] + dp[n][3]) % mod
			return result
			Citire date de intrare

	~~# Calcul numărul de numere~~		n = int(input())
	~~for i in range(2,~~ n ~~+ 1):~~
	~~dp[i][1]~~ = (~~dp[i - 1][2] + dp[i - 1][3]) % mod~~
	~~dp[i][2] =~~ (~~dp[i - 1][1] + dp[i - 1][3]~~) ~~% mod~~
	~~dp[i][3] = (dp[i - 1][1] + dp[i - 1][2]~~) ~~% mod~~

	~~result = (dp[n][1] + dp[n][2] + dp[n][3]) % mod~~		Calcul și afișare rezultat
	~~return result~~

	~~# Citire date de intrare~~
	~~n = int(input())~~

	~~# Calcul și afișare rezultat~~		result = count_numbers(n) print(result)
	result = count_numbers(n)		</syntaxhighlight>
	print(result)

Mraa: Pagină nouă: ==Cerința== Se dă un număr natural nenul n. Să se determine numărul de numere de n cifre din mulțimea {1, 2, 3, 4} care nu au două cifre alăturate egale și care au proprietatea că sunt divizibile cu 2. Pentru că acest număr poate fi foarte mare, se va calcula 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 cerut, modulo 123457. Restricții și precizări Pentru 80 de p...

2023-12-11T16:07:11Z

Pagină nouă: ==Cerința== Se dă un număr natural nenul n. Să se determine numărul de numere de n cifre din mulțimea {1, 2, 3, 4} care nu au două cifre alăturate egale și care au proprietatea că sunt divizibile cu 2. Pentru că acest număr poate fi foarte mare, se va calcula 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 cerut, modulo 123457. Restricții și precizări Pentru 80 de p...

New page

==Cerința==
Se dă un număr natural nenul n. Să se determine numărul de numere de n cifre din mulțimea {1, 2, 3, 4} care nu au două cifre alăturate egale și care au proprietatea că sunt divizibile cu 2. Pentru că acest număr poate fi foarte mare, se va calcula 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 cerut, modulo 123457.

Restricții și precizări
Pentru 80 de puncte, 1 ≤ n ≤ 10.000
Pentru alte 20 de puncte, 100.000.000 ≤ n ≤ 1.000.000.000
==Exemplu==:
Intrare

2
Ieșire

6
==Explicație==
Numerele sunt 12, 14, 24, 32, 34, 42.
==Rezolvare==
def count_numbers(n):
mod = 123457

# Inițializare vector dp
dp = [[0] * 4 for _ in range(n + 1)]
for i in range(1, 4):
dp[1][i] = 1

# Calcul numărul de numere
for i in range(2, n + 1):
dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod
dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod
dp[i][3] = (dp[i - 1][1] + dp[i - 1][2]) % mod

result = (dp[n][1] + dp[n][2] + dp[n][3]) % mod
return result

# Citire date de intrare
n = int(input())

# Calcul și afișare rezultat
result = count_numbers(n)
print(result)