Đôrêmon chinh phục tình yêu

Xem PDF

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

Đôrêmon - chàng trai có sở thích rất đặc biệt là chinh phục trái tim của các cô gái. Đôrêmon thường hay sang nhà bác ở làng bên cạnh chơi vừa để thăm bác vừa để ngắm nhìn các cô gái. Các cô gái ở làng này cũng rất thích Đôrêmon và cô nào cũng muốn được anh chàng này chinh phục. Bác của Đôrêmon là một người rất vui tính và cũng muốn thử tài của thằng cháu mình nên đã nói với Đôrêmon: “ Trong làng bác có rất nhiều cô gái xinh đẹp, tài năng. Các cô gái ấy đều được đánh một mã số gọi là mã khóa tình yêu. Các mã số đều có \(n\) chữ số và các chữ số đều là 01, không mã số nào trùng nhau. Nếu cháu tìm được mã số nào không chứa quá \(k\) chữ số 0 hoặc chữ số 1 liên tiếp nhau thì cháu sẽ được chinh phục cô gái ấy.” Đôrêmon rất sung sướng và muốn đếm thật nhanh mình có thể chinh phục bao nhiêu cô gái nhưng chuối cái là anh chàng này lại không biết làm cách nào. Bạn hãy giúp Đôrêmon đếm nhé.

Yêu cầu: Hãy đếm số cô gái mà Đôrêmon có thể chinh phục?

Input

  • Gồm 1 dòng duy nhất chứa 2 số \(n\)\(k\). \((2 \leq k \leq n \leq 1000).\)

Output

  • Gồm 1 số duy nhất là số cô gái mà Đôrêmon có thể chinh phục.

Scoring

  • Subtask \(1\) (\(15\%\) số điểm): độ dài mã số không vượt quá \(15\).
  • Subtask \(2\) (\(15\%\) số điểm): độ dài mã số không vượt quá \(300\).
  • Subtask \(1\) (\(70\%\) số điểm): độ dài mã số không vượt quá \(1000\).

Example

Test 1

Input
3 2 
Output
6
Note

Gồm các xâu \((001, 010, 011, 100, 101, 110)\)

Test 1

Input
4 2 
Output
10
Note

Gồm các xâu \((0010, 0011, 0100, 0110, 0101, 1001, 1010, 1011, 1100, 1101)\)


Bình luận

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