Leo Thang

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 977M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một chiếc cầu thang có n bậc, một người nào đó có thể bước một bước lên một, hai hoặc ba bậc. Hỏi để lên hết n bậc thang thì người đó có bao nhiêu cách leo thang

Input

Một số nguyên dương 1<=n<=20

Output

Một số nguyên dương là số cách lên n bậc thang

Example

Input

4

Output

7

Giải thích: Có thể có các cách lên sau

Cách 1: 1+1+1+1 (Bước từng bậc)

Cách 2: 2+1+1 (Bước đầu 2 bậc sau đó là từng bậc)

Cách 3: 1+2+1

Cách 4: 1+1+2

Cách 5: 1+3

Cách 6: 3+1

Cách 7: 2+2

tichpx

Comments


  • 0
    EchVaVit  commented on May 2, 2025, 3:10 a.m.

    .lua

    local a = {}

local function compute_values(n)
    a[1] = 1
    a[2] = 2
    a[3] = 4

    for i = 4, n do
        a[i] = a[i - 3] + a[i - 2] + a[i - 1]
    end
end

local n = io.read("*n")

compute_values(n)

print(a[n])