3990 - Dinamica 09: Difference between revisions
Pagină nouă: ==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 p... |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 21: | Line 21: | ||
Numerele sunt 12, 14, 24, 32, 34, 42. | Numerele sunt 12, 14, 24, 32, 34, 42. | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3" line="1"> | |||
def count_numbers(n): | 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) | |||
result = count_numbers(n) | </syntaxhighlight> | ||
print(result) | |||
Latest revision as of 18:25, 11 January 2024
Cerința[edit | edit source]
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[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 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[edit | edit source]
Numerele sunt 12, 14, 24, 32, 34, 42.
Rezolvare[edit | edit source]
<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>