Fişierul intrare/ieşire: | scara.in, scara.out | Sursă | ad-hoc |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 1 sec | Limită de memorie | 512 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Scara
Notă importantă: această problemă a fost modificată faţă de original, în data de 25.10.2013, deoarece testul 10 avea n 10 000 000 iar restricţia originală era n ≤ 1 000 000. Am relaxat restricţia la n ≤ 1 000 000
Copilul Andrei vrea sa stie in cate moduri poate sa urce scara. Fiind mutant, el poate sa urce o treapta, doua, pana la k trepte deodata.
(Din pacate nu vrea sa se foloseasca de celalte super-puteri)
Date de intrare
Se da n si k, unde n reprezinta numarul de trepte ale scarii si k reprezinta numarul maxim de trepte pe care le poate urca mutantul la un pas.
Date de ieşire
Numarul de moduri de a urca scara modulo 1999999973
Restricţii
- n ≤ 10 000 000
- k ≤ 100
Exemplu
scara.in | scara.out |
---|---|
3 2 | 3 |
Explicaţie
Cele 3 moduri de a urca scara sunt:
1 1 1
1 2
2 1