Editing 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>