시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 12 | 5 | 5 | 41.667% |
A word s composed of (2n + n - 1) characters 0
and 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 0001011100
.
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 (0
or 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 0
and 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
2
After adding the characters 01
we obtain the following t.t.d.B.s. of order 3: 0010101
.
Contest > Algorithmic Engagements > PA 2009 7-1번