2259 - Dinamica 01

Se consideră un număr natural nenul N. Vom considera mulțimea A(N) a numerelor de N cifre nenule care au proprietatea că orice două cifre alăturate sunt de parități diferite. De exemplu 1472 este un număr din mulțimea A(4), dar 1567 nu este pentru că are cifrele alăturate 1 și 5 de aceeași paritate.

Cerința

Să se determine numărul de elemente ale mulțimii A(N). Pentru că acest număr poate fi foarte mare, se va determina modulo 30103.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând numărul modulo 30103 al elementelor mulțimii A(N).

Restricții și precizări

1 ≤ n ≤ 100.000 ==Exemplu==: Intrare

2 Ieșire

Rezolvare

<syntaxhighlight lang="python3" line="1"> MOD = 30103

def numar_elemente_multime(N):

  # Inițializăm matricea dp cu 0-uri
  dp = [[0] * 2 for _ in range(N + 1)]
  # Pentru un singur caracter, avem 9 opțiuni (de la 1 la 9)
  dp[1][0] = 9
  dp[1][1] = 0
  # Calculăm numărul de elemente pentru N cifre
  for i in range(2, N + 1):
      dp[i][0] = (dp[i - 1][0] * 9 + 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_elemente_multime(N)
  
  print(rezultat)

</syntaxhighlight>