Rezolvare completă PbInfo #1991 Trepte2

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Trepte2:

/// 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];
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1991 Trepte2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1991 Trepte2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!