← 返回题目列表

Codeforces · 2154/A

A. 笔记锁

中文机器翻译题面 查看原题

Teto 正在玩热门节奏游戏 奥苏!。游戏可以用长度为 $$$n$$$ 的二进制字符串 $$$^{\text{*}}$$$ $$$s$$$ 和正整数 $$$k$$$ 来描述,其中将按顺序发生以下情况:

  • 您将选择 $$$s$$$ 中的一些头寸进行保护。
  • 然后,对于按升序排列的每个 $$$i$$$ ($$$1 \le i \le n$$$),如果满足以下所有条件,Teto 可以将 $$$s_i$$$ 设置为 $$$\mathtt{0}$$$:
    • $$$s_i = \mathtt{1}$$$,
    • $$$s_i$$$ 不受保护,
    • 前面的 $$$k - 1$$$ 元素不包含 $$$\mathtt{1}$$$。更正式地说,$$$\mathtt{1}$$$ 不会出现在 $$$s_{\max(1, i - k + 1)},\ldots,s_{i - 1}$$$ 中。

你不喜欢 Teto(出于某种原因)。因此,请确定您需要保护的最少位置数,以迫使她保持 $$$s$$$ 不变。

$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的字符串。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 1000$$$; $$$2 \le k \le n$$$) — $$$s$$$ 和 $$$k$$$ 的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。

所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

输出

对于每个测试用例,输出需要保护的最小位置数,以强制 Teto 保持字符串不变。

示例

输入
复制

9
2 2
11
6 6
100001
5 3
10000
7 2
1010101
7 4
0000001
3 3
010
3 2
011
7 4
1001001
8 3
00000000

输出
复制

1
1
1
4
1
1
1
1
0

注意

对于第一个测试用例,您可以保护第一个元素并具有:$$$s = \mathtt{\color{red}{1}1}$$$。现在 Teto 无法更改 $$$s_1$$$,因为它受到保护,并且无法更改 $$$s_2$$$,因为 $$$s_1 = \mathtt{1}$$$。可以证明这是最优的。

对于第二个测试用例,您只能保护第一个元素,并且 $$$s = \color{red}{\mathtt{1}}\mathtt{00001}$$$。 Teto 无法更改 $$$s_1$$$,因为它受到保护,并且她无法更改 $$$s_6$$$,因为前面的 $$$k - 1$$$ 元素中有 $$$\mathtt{1}$$$ ($$$\color{blue}{\mathtt{10000}}\mathtt{1}$$$)。

对于第四个测试用例,您必须保护 $$$s_1,s_3,s_5,s_7$$$ 并让 $$$s = \mathtt{\color{red}{1}0\color{red}{1}0\color{red}{1}0\color{red}{1}}$$$。可以证明这是最优的。例如,如果您没有保护 $$$s_3$$$,则 Teto 可以将其更改为 $$$\mathtt{0}$$$ ($$$\mathtt{\color{red}{1}\color{blue}{0}10\color{red}{1}0\color{red}{1}}$$$)