2260 - Dinamica 02 - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:27:06Z

Rezolvare

← Older revision		Revision as of 18:27, 11 January 2024
Line 22:		Line 22:

	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 777013		MOD = 777013

Mraa at 17:31, 11 January 2024

2024-01-11T17:31:50Z

← Older revision		Revision as of 17:31, 11 January 2024
Line 22:		Line 22:

	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 777013		MOD = 777013

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

	# Pentru un singur caracter, avem 26 opțiuni (literele mici de la 'a' la 'z')		# Inițializăm matricea dp cu 0-uri
	dp[1][0] = 26		dp = [[0] * 2 for _ in range(N + 1)]
	dp[1][1] = 0		# Pentru un singur caracter, avem 26 opțiuni (literele mici de la 'a' la 'z')
			dp[1][0] = 26
			dp[1][1] = 0
			# Calculăm numărul de cuvinte pentru N caractere
			for i in range(2, N + 1):
			dp[i][0] = (dp[i - 1][0] * 25 + 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 cuvinte pentru N caractere~~		if __name__ == "__main__":
	~~for i in range(2, N + 1):~~
	~~dp[i][0]~~ = ~~(dp[i - 1][0] * 25 + 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_cuvinte(N)
	N = int(input("Introduceți N: "))
			print(rezultat)
	rezultat = numar_cuvinte(N)		</syntaxhighlight>

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

Mraa: Pagină nouă: Se consideră un număr natural nenul N. ==Cerința== Să se determine numărul de cuvinte de lungime N formate doar din litere mici și cu proprietatea că nu pot exista trei litere alăturate identice. Pentru că acest număr poate fi foarte mare, se va determina modulo 777013. ==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 cuvinte modulo 777013. ==Restricții și precizări== 1 ≤ N ≤...

2023-12-21T20:49:19Z

Pagină nouă: Se consideră un număr natural nenul N. ==Cerința== Să se determine numărul de cuvinte de lungime N formate doar din litere mici și cu proprietatea că nu pot exista trei litere alăturate identice. Pentru că acest număr poate fi foarte mare, se va determina modulo 777013. ==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 cuvinte modulo 777013. ==Restricții și precizări== 1 ≤ N ≤...

New page

Se consideră un număr natural nenul N.

==Cerința==
Să se determine numărul de cuvinte de lungime N formate doar din litere mici și cu proprietatea că nu pot exista trei litere alăturate identice. Pentru că acest număr poate fi foarte mare, se va determina modulo 777013.

==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 cuvinte modulo 777013.

==Restricții și precizări==
1 ≤ N ≤ 1 000 000
Cuvintele baaad și deeeeef au trei litere alăturate egale, pe când abbaa și xxyyxx nu au.
==Exemplu==:
Intrare

2
Ieșire

676

==Rezolvare==
MOD = 777013

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

# Pentru un singur caracter, avem 26 opțiuni (literele mici de la 'a' la 'z')
dp[1][0] = 26
dp[1][1] = 0

# Calculăm numărul de cuvinte pentru N caractere
for i in range(2, N + 1):
dp[i][0] = (dp[i - 1][0] * 25 + 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_cuvinte(N)

print(rezultat)
python numar_cuvinte.py