Pseudo Pseudo Random Numbers

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이 n인 비트 문자열 중에서 같은 비트가 k개를 넘게 연속하지 않는 문자열의 개수를 센다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

It turns out that if numbers were truly random, then each possible bit string (string of 0’s and 1’s) of length n would be equally likely. For example, 111111 would be just as likely as 010110 to occur. Unfortunately, most people believe that any time they see the same bit over and over again, that the process can't be truly random.

You are in charge of generating random bit strings of length n for use in a video game. However, the producer of the game has asked you to remove all possibilities where there are more than k 0’s or 1’s in a row. For example, if n = 4 and k = 2, then the 10 valid bit strings would be 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, and 1101 (the other 6 strings of 4 bits either have more than two 0’s in a row or more than two 1’s in a row, so they are not valid).

Given the values of n and k, determine the number of n bit strings that do not contain any runs of 0’s or 1’s of length greater than k.

입력

There is only one input line; it contains two integers: n (2 ≤ n ≤ 20), indicating the length of the bit string for the problem, and k (1 ≤ k ≤ n), indicating the maximal length of a run of 0’s or 1’s for the bit strings to be created.

출력

Print the number of valid bit strings of length n that do not contain any runs of the same bit of length greater than k.

예제3

예제 1
입력
```
4 2
```
예상 출력
```
10
```
예제 2
입력
```
5 1
```
예상 출력
```
2
```
예제 3
입력
```
20 20
```
예상 출력
```
1048576
```