| Good Egg Galaxy — Koji Kondo,《超级马里奥银河》 |
![]() |
令 $$$n$$$ 为正整数。 Mario 有一个长度为 $$$n$$$ 的二进制字符串$$$^{\text{∗}}$$$ $$$s$$$。在一步中,他可以选择任意位置 $$$i$$$ ($$$2 \leq i \leq n-1$$$) ,使其位于两个位置之间 1's,即 $$$s_{i-1} = s_{i+1} = \texttt{1}$$$,然后将 $$$s_i$$$ 设置为 0 or 1.
Mario 可以根据需要多次执行此操作(可能为零)。最小和最大数量是多少 1可以出现在结果字符串中吗?
$$$^{\text{*}}$$$二进制字符串是一个字符串,其字符是 0 or 1.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 100$$$) — 字符串的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符组成 0 or 1.
输出
对于每个测试用例,输出两个整数——最小和最大数量 1位于经过一定次数的移动后生成的字符串中。
示例
输入复制
431116011011710111019100101101
输出复制
2 33 54 75 7
注意
在第一个测试用例中,最小数量 1可以出现在结果字符串中的是 $$$2$$$。这是通过如下转换字符串来完成的: $$\mathtt{1}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{101}.$$ 的最大数量 1可以出现在结果字符串中的是 $$$3$$$,无需执行任何操作。
在第二个测试用例中,最小数量 1可以出现在结果字符串中的是 $$$3$$$。这是通过如下方式转换字符串来完成的: $$\mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{01}\underline{\mathtt{1}}\mathtt{111} \to \mathtt{0101}\underline{\mathtt{1}}\mathtt{1} \to \mathtt{010101}.$$ 的最大数量 1可以出现在结果字符串中的是 $$$5$$$。这是通过如下转换字符串来完成的: $$\mathtt{011}\underline{\mathtt{0}}\mathtt{11} \to \mathtt{011111}.$$
