# PBinfo #1991 – Trepte2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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 este pe 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 ≤ 100.000
1 ≤ k ≤ n - 1
deoarece numărul va fi prea mare sa va afișa modulo 9001.

Exemplul 1:
Intrare

2 2
Ieșire

1
Explicație
Există o soluție, aceea când sare direct pe treapta 2.

Exemplul 2:
Intrare

4 2
Ieșire

3
Explicație
Prima: 1 -> 2 -> 3 -> 4
A doua: 1 -> 2 -> 4
A treia: 1 -> 3 -> 4

## Cod sursă C++

```cpp
/// Solutie - Moca Andrei - 100p
#include <bits/stdc++.h>
int nr[100002]; /// nr[i] - nr de modalitati de a ajunge pe treapta i
int n, k;
int main()
{
	std::cin >> n >> k;
	nr[0] = 1;
	nr[1] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= k && j < i; j++)
        {
            nr[i] += nr[i - j];
            if (nr[i] > 9001)
                nr[i] -= 9001;
        }
	std::cout << nr[n];
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1991)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1991/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1991/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)