2259 - Dinamica 01: Difference between revisions
Pagină nouă: 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 intrar... |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 17: | Line 17: | ||
Ieșire | Ieșire | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3" line="1"> | |||
MOD = 30103 | MOD = 30103 | ||
def numar_elemente_multime(N): | 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> | |||
Latest revision as of 18:26, 11 January 2024
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[edit | edit source]
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[edit | edit source]
Programul citește de la tastatură numărul N.
Date de ieșire[edit | edit source]
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[edit | edit source]
1 ≤ n ≤ 100.000 ==Exemplu==: Intrare
2 Ieșire
Rezolvare[edit | edit source]
<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>