Fișierul intrare/ieșire scara.in, scara.out Sursă ad-hoc
Autor din folclor Adăugată de avatar xiofurry Neagu Rares xiofurry
Timp de execuție pe test 1 sec Limită de memorie 512 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici