Tung đồng xu

View as PDF

Submit solution


Points: 100.00 (partial)
Time limit: 3.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Ngày xưa, cách đây đã lâu lắm rồi, ở vương quốc Byteland tươi đẹp có một nàng công chúa xinh đẹp tuyệt trần. Thật không may, chính vì sự xinh đẹp đó đã làm phù thủy Astral đã bắt làm về làm người hầu cho ông ta. Đức Vua vô cùng hoang mang khi chuyện này xảy ra, ông không biết phải làm cách nào để giải cứu con mình (ông không thể mang quân đến đánh vì điều đó là vô nghĩa). Tuy nhiên, tên phù thủy này lại rất sợ một câu thần chú được suy ra từ việc giải một bài toán cổ của Thần Sphinx. Bài toán đó có thể được mô tả một cách đơn giản như sau: “Khi ta tung một đồng xu, ta sẽ nhận được mặt sấp hoặc ngửa. Nếu ta tung lần lượt N đồng xu thì có bao nhiêu trường hợp mà có ít nhất K đồng xu liên tiếp cùng là ngửa ?” . Đức vua hứa sẽ thưởng rất hậu hĩnh và gả công chúa cho ai giải được bài toán này. Thực ra công chúa và anh chàng làm vườn trong hoàng cung đã yêu thương nhau từ lâu. Anh chàng giờ đây đang rất bối rối và cần sự giúp đỡ của bạn.

Dữ liệu:
  • Một dòng duy nhất ghi hai số N và K.
Kết quả:
  • Một dòng duy nhất ghi số trường hợp đếm được.

Giới hạn: 1 ≤ K ≤ N ≤ 10000

Ví dụ
INPUT
4 2
OUTPUT
8

Comments

Please read the guidelines before commenting.


There are no comments at the moment.