2259 - Dinamica 01 - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:26:42Z

Rezolvare

← Older revision		Revision as of 18:26, 11 January 2024
Line 17:		Line 17:
	Ieșire		Ieșire
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 30103		MOD = 30103

Mraa at 17:30, 11 January 2024

2024-01-11T17:30:53Z

← Older revision		Revision as of 17:30, 11 January 2024
Line 17:		Line 17:
	Ieșire		Ieșire
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 30103		MOD = 30103

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

	# Pentru un singur caracter, avem 9 opțiuni (de la 1 la 9)		# Inițializăm matricea dp cu 0-uri
	dp[1][0] = 9		dp = [[0] * 2 for _ in range(N + 1)]
	dp[1][1] = 0		# Pentru un singur caracter, avem 9 opțiuni (de la 1 la 9)
			dp[1][0] = 9
			dp[1][1] = 0
			# Calculăm numărul de elemente pentru N cifre
			for i in range(2, N + 1):
			dp[i][0] = (dp[i - 1][0] * 9 + dp[i - 1][1]) % MOD
			dp[i][1] = dp[i - 1][0]
			return (dp[N][0] + dp[N][1]) % MOD

	~~# Calculăm numărul de elemente pentru N cifre~~		if __name__ == "__main__":
	~~for i in range(2, N + 1):~~
	~~dp[i][0]~~ = ~~(dp[i - 1][0] * 9 + dp[i - 1][1]) % 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 = numar_elemente_multime(N)
	N = int(input("Introduceți N: "))
			print(rezultat)
	rezultat = numar_elemente_multime(N)		</syntaxhighlight>

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

Mraa: Pagină nouă: Se consideră un număr natural nenul N. Vom considera mulțimea A(N) a numerelor de N cifre nenule care au proprietatea că orice două cifre alăturate sunt de parități diferite. De exemplu 1472 este un număr din mulțimea A(4), dar 1567 nu este pentru că are cifrele alăturate 1 și 5 de aceeași paritate. ==Cerința== Să se determine numărul de elemente ale mulțimii A(N). Pentru că acest număr poate fi foarte mare, se va determina modulo 30103. ==Date de intrar...

2023-12-21T20:44:06Z

Pagină nouă: Se consideră un număr natural nenul N. Vom considera mulțimea A(N) a numerelor de N cifre nenule care au proprietatea că orice două cifre alăturate sunt de parități diferite. De exemplu 1472 este un număr din mulțimea A(4), dar 1567 nu este pentru că are cifrele alăturate 1 și 5 de aceeași paritate. ==Cerința== Să se determine numărul de elemente ale mulțimii A(N). Pentru că acest număr poate fi foarte mare, se va determina modulo 30103. ==Date de intrar...

New page

Se consideră un număr natural nenul N. Vom considera mulțimea A(N) a numerelor de N cifre nenule care au proprietatea că orice două cifre alăturate sunt de parități diferite. De exemplu 1472 este un număr din mulțimea A(4), dar 1567 nu este pentru că are cifrele alăturate 1 și 5 de aceeași paritate.

==Cerința==
Să se determine numărul de elemente ale mulțimii A(N). Pentru că acest număr poate fi foarte mare, se va determina modulo 30103.

==Date de intrare==
Programul citește de la tastatură numărul N.
==Date de ieșire==
Programul va afișa pe ecran numărul S, reprezentând numărul modulo 30103 al elementelor mulțimii A(N).

==Restricții și precizări==
1 ≤ n ≤ 100.000
==Exemplu==:
Intrare

2
Ieșire
==Rezolvare==
MOD = 30103

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

# Pentru un singur caracter, avem 9 opțiuni (de la 1 la 9)
dp[1][0] = 9
dp[1][1] = 0

# Calculăm numărul de elemente pentru N cifre
for i in range(2, N + 1):
dp[i][0] = (dp[i - 1][0] * 9 + dp[i - 1][1]) % 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 = numar_elemente_multime(N)

print(rezultat)
python multimi.py