3661 - Dinamica 05

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

<syntaxhighlight lang="python3" line="1"> 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 </syntaxhighlight>