|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
A word s composed of (2n + n - 1) characters
1 is called a de Bruijn sequence of order n if every n-character word composed of zeroes and ones is its subword - that is a fragment of consecutive characters - of s. An example of a de Bruijn sequence of order 3 is
A type two de Bruijn sequence of order n is such a word s of arbitrary length that each n-character word composed of zeroes and ones is a subsequence - that is a fragment of not necessarily consecutive characters - of s. An example of a type two de Bruijn sequence of order 3 is
00101101. As far as we know, Nicolaas Govert de Bruijn did not invent such sequences, but their definition is similar to the previous one, isn't it?
Let us consider a word s composed only of zeroes and ones. How many digits (
1, of course) have to be added at the end of s for the word to become a type two de Bruijn sequence of order n?
The first line of the standard input contains two integers m and n (1 ≤ m, n ≤ 1,000,000), separated by a single space. The second line contains an m-character word s composed only of digits
1 that does not contain any spaces.
The first and only line of the standard output should contain a single non-negative integer, denoting the minimal number of digits that need to be added at the end of the word s for it to become a t.t.d.B.s. of order n.
5 3 00101
After adding the characters
01 we obtain the following t.t.d.B.s. of order 3: