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

View as PDF

Submit solution

Points: 200 (partial)
Time limit: 1.0s
Memory limit: 1023M
Input: stdin
Output: stdout

Author:
Problem types

Đô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?

Dữ liệu

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

Kết quả

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

Input

3 2

Output

6

Giải thích: Gồm các xâu (001, 010, 011, 100, 101, 110)

Input

4 2

Output

10

Giải thích: Gồm các xâu (0010, 0011, 0100, 0110, 0101, 1001, 1010, 1011, 1100, 1101)

Ràng buộc

  • Subtask 1: 15% số test ứng với độ dài mã số không vượt quá 15.
  • Subtask 2: 15% test ứng với độ dài mã số không vượt quá 300.
  • Subtask 3: Các test còn lại ứng với độ dài mã số không vượt quá 1000.

Nguồn: CĐ DHDBBB 2020


Be the first to comment

Comments

There are no comments at the moment.