3217 - Trepte 2.2: Difference between revisions
Pagină nouă: ==Cerința== O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial se afla treapta 1) ==Date de intrare== Programul citește de la tastatură numerele n și k. ==Date de ieșire== Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte. ==Restricții și precizări== 1 < n ≤ 1.000.000; 1... |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 35: | Line 35: | ||
A treia: 1 -> 3 -> 4 | A treia: 1 -> 3 -> 4 | ||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python3" line="1"> | |||
def numar_moduri_urcare_trepte(n, k): | def numar_moduri_urcare_trepte(n, k): | ||
mod = 9001 | |||
# Inițializare vector dp | |||
dp = [0] * (n + 1) | |||
dp[1] = 1 | |||
# Calcul numărul de moduri | |||
for i in range(1, n + 1): | |||
for j in range(1, k + 1): | |||
if i + j <= n: | |||
dp[i + j] = (dp[i + j] + dp[i]) % mod | |||
return dp[n] | |||
Citire date de intrare | |||
n, k = map(int, input().split()) | |||
Calcul și afișare rezultat | |||
result = numar_moduri_urcare_trepte(n, k) print(result) | |||
result = numar_moduri_urcare_trepte(n, k) | </syntaxhighlight> | ||
print(result) | |||
Latest revision as of 18:24, 11 January 2024
Cerința[edit | edit source]
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial se afla treapta 1)
Date de intrare[edit | edit source]
Programul citește de la tastatură numerele n și k.
Date de ieșire[edit | edit source]
Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.
Restricții și precizări[edit | edit source]
1 < n ≤ 1.000.000; 1 ≤ k ≤ n - 1; deoarece numărul va fi prea mare sa va afișa modulo 9001; la început, persoana se află pe treapta 1. ==Exemplul 1==: Intrare
2 2 Ieșire
1
Explicație[edit | edit source]
Există o soluție, aceea când sare direct pe treapta 2.
==Exemplul 2==: Intrare
4 2 Ieșire
3
Explicație[edit | edit source]
Prima: 1 -> 2 -> 3 -> 4 A doua: 1 -> 2 -> 4 A treia: 1 -> 3 -> 4
Rezolvare[edit | edit source]
<syntaxhighlight lang="python3" line="1"> def numar_moduri_urcare_trepte(n, k):
mod = 9001
# Inițializare vector dp
dp = [0] * (n + 1)
dp[1] = 1
# Calcul numărul de moduri
for i in range(1, n + 1):
for j in range(1, k + 1):
if i + j <= n:
dp[i + j] = (dp[i + j] + dp[i]) % mod
return dp[n]
Citire date de intrare
n, k = map(int, input().split())
Calcul și afișare rezultat
result = numar_moduri_urcare_trepte(n, k) print(result) </syntaxhighlight>