Tung đồng xu

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

Small

Dạng bài

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ngày xưa, cách đây đã lâu lắm rồi, ở vương quốc Byteland tươi đẹp có một nàng công chúa xinh đẹp tuyệt trần. Thật không may, chính vì sự xinh đẹp đó đã làm phù thủy Astral đã bắt làm về làm người hầu cho ông ta. Đức Vua vô cùng hoang mang khi chuyện này xảy ra, ông không biết phải làm cách nào để giải cứu con mình (ông không thể mang quân đến đánh vì điều đó là vô nghĩa). Tuy nhiên, tên phù thủy này lại rất sợ một câu thần chú được suy ra từ việc giải một bài toán cổ của Thần Sphinx. Bài toán đó có thể được mô tả một cách đơn giản như sau: "Khi ta tung một đồng xu, ta sẽ nhận được mặt sấp hoặc ngửa. Nếu ta tung lần lượt \(N\) đồng xu thì có bao nhiêu trường hợp mà có ít nhất \(K\) đồng xu liên tiếp cùng là ngửa?". Đức vua hứa sẽ thưởng rất hậu hĩnh và gả công chúa cho ai giải được bài toán này. Thực ra công chúa và anh chàng làm vườn trong hoàng cung đã yêu thương nhau từ lâu. Anh chàng giờ đây đang rất bối rối và cần sự giúp đỡ của bạn.

Input

Một dòng duy nhất ghi hai số \(N\) và \(K\) (\(1\leq K\leq N\leq 10000\))

Output

Một dòng duy nhất ghi số trường hợp đếm được.

Example

Test 1

Input

4 2

Output

Nguồn: SPOJ

Bình luận

Không có bình luận nào.