3990 - Dinamica 09

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

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