3661 - Dinamica 05 - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:24:53Z

Rezolvare

← Older revision		Revision as of 18:24, 11 January 2024
Line 19:		Line 19:
	Ieșire		Ieșire
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	def count_words(n, p):		def count_words(n, p):

Mraa at 17:26, 11 January 2024

2024-01-11T17:26:55Z

@@ Line 19: / Line 19: @@
 Ieșire
 ==Rezolvare==
 def count_words(n, p):
-    # a) Numărul cuvintelor fără două litere identice alăturate
+   mod = 123457
-    dp_a = [[0] * 2 for _ in range(n + 1)]
+   # a) Numărul cuvintelor fără două litere identice alăturate
-    dp_a[1][0] = 26  # o literă mică
+   dp_a = [[0] * 2 for _ in range(n + 1)]
-    dp_a[1][1] = 26  # o literă mare
+   dp_a[1][0] = 26  # o literă mică
-    for i in range(2, n + 1):
+n, p = map(int, input().split())
-    for i in range(2, n + 1):
+Calcul și afișare rezultat
-# Calcul și afișare rezultat
+result = count_words(n, p) print(*result)
 2028 651

Mraa: Pagină nouă: ==Cerința== Se dau numerele naturale n și p. Să se determine: a) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că aceste cuvinte nu pot avea două litere alăturate identice, indiferent că sunt mari sau mici (cuvintele baArda sau fEEric au două litere alăturate identice). b) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că nu pot apărea două litere mari pe poziții alăturate....

2023-12-11T16:04:53Z

Pagină nouă: ==Cerința== Se dau numerele naturale n și p. Să se determine: a) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că aceste cuvinte nu pot avea două litere alăturate identice, indiferent că sunt mari sau mici (cuvintele baArda sau fEEric au două litere alăturate identice). b) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că nu pot apărea două litere mari pe poziții alăturate....

New page

==Cerința==
Se dau numerele naturale n și p. Să se determine:
a) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că aceste cuvinte nu pot avea două litere alăturate identice, indiferent că sunt mari sau mici (cuvintele baArda sau fEEric au două litere alăturate identice).
b) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că nu pot apărea două litere mari pe poziții alăturate.
c) numărul cuvintelor de lungime n formate doar din litere mici și cu proprietatea că au cel mult p vocale (vocalele fiind: a, e, i, o, u)

==Date de intrare==
Programul citește de la tastatură numerele n și p.

==Date de ieșire==
Programul va afișa pe ecran trei numere: X, Y și Z, separate prin spațiu, care vor reprezenta răspunsurile la cele trei cerințe. Pentru că aceste numere pot fi foarte mari, se vor determina modulo 123457

==Restricții și precizări==
1 ≤ p < n ≤ 1.000
==Exemplu==:
Intrare

2 1
Ieșire
==Rezolvare==
def count_words(n, p):
mod = 123457

# a) Numărul cuvintelor fără două litere identice alăturate
dp_a = [[0] * 2 for _ in range(n + 1)]
dp_a[1][0] = 26 # o literă mică
dp_a[1][1] = 26 # o literă mare

for i in range(2, n + 1):
dp_a[i][0] = (dp_a[i - 1][0] + dp_a[i - 1][1]) % mod
dp_a[i][1] = dp_a[i - 1][0]

X = (dp_a[n][0] + dp_a[n][1]) % mod

# b) Numărul cuvintelor fără două litere mari consecutive
dp_b = [0] * (n + 1)
dp_b[1] = 52 # o literă mică sau mare

for i in range(2, n + 1):
dp_b[i] = dp_b[i - 1] * 2 - dp_b[i - 2]

Y = dp_b[n]

# c) Numărul cuvintelor mici cu cel mult p vocale
dp_c = [[0] * (p + 1) for _ in range(n + 1)]
dp_c[1][0] = 25 # o literă mică fără vocală

for i in range(2, n + 1):
dp_c[i][0] = (dp_c[i - 1][0] * 25) % mod
for j in range(1, min(i, p) + 1):
dp_c[i][j] = (dp_c[i - 1][j] * 25 + dp_c[i - 1][j - 1]) % mod

Z = sum(dp_c[n][:p + 1]) % mod

return X, Y, Z

# Citire date de intrare
n, p = map(int, input().split())

# Calcul și afișare rezultat
result = count_words(n, p)
print(*result)

2600 2028 651