Đếm số cách leo cầu thang với bước dài từ 1 tới k
Bản mở rộng của bài leo cầu thang kinh điển: thay vì chỉ hai cỡ bước 1 và 2, người ta
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, loops.
Nội dung đề bài
Mô tả bài toán
Bản mở rộng của bài leo cầu thang kinh điển: thay vì chỉ hai cỡ bước 1 và 2, người ta cho phép mọi cỡ bước từ 1 tới k. Bước cuối cùng vì thế có k khả năng, và ta phải cộng đúng k trạng thái trước đó.
Yêu cầu
Cho hai số nguyên n và k. Hãy đếm số dãy bước khác nhau để đi từ bậc 0 lên đúng bậc n, biết rằng mỗi bước có độ dài là một số nguyên bất kỳ trong đoạn [1, k].
Quy ước nộp bài
Nộp tệp solution.cpp đọc n và k từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Một dòng duy nhất chứa hai số nguyên n và k, cách nhau bởi dấu cách
(1 <= k <= n <= 40).
Output
- Một số nguyên trên một dòng là số cách leo hết cầu thang. Kết quả có thể lớn, ví dụ
n = k = 40 cho 549755813888.
Ràng buộc
- 1 <= k <= n <= 40, kết quả vừa long long.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
5 2
Output
8
Ví dụ 2
Input
4 4
Output
8
Giải thích
Với k = 2 ta trở về bài leo cầu thang quen thuộc và có 8 cách, nên in ra:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
