← 返回题目
题库练习 1-1
← 上一题 下一题 →

A16507 | 1-1

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

[Good Egg Galaxy — Koji Kondo, Super Mario Galaxy ](https://www.youtube.com/watch?v=56TfZJoZxv8)
![](/uploads/acgo/image/c117ceb1920a479aa4aaf07348c183a5_99f6309c62f1.png)

设 $n$ 为一个正整数。Mario 有一个长度为 $n$ 的二进制串 $s$。

每一步操作中，他可以选择任意一个位置 $i$（$2 \leq i \leq n-1$），该位置需要同时满足它的左右相邻位置都是 $1$，即 $s_{i-1} = s_{i+1} = 1$，然后将 $s_i$ 改为 $0$ 或 $1$。

Mario 可以进行任意次数（也可以一次都不做）上述操作。请你求出最终字符串中 $1$ 的最小个数和最大个数分别是多少？

注：二进制串是指所有字符都是 $0$ 或 $1$ 的字符串。

输入格式

每组测试数据包含多个测试用例。第一行输入一个整数 $t$（$1 \leq t \leq 500$），表示测试用例数量。

每个测试用例的第一行输入一个整数 $n$（$3 \leq n \leq 100$），表示字符串的长度。

每个测试用例的第二行输入一个长度为 $n$ 的二进制串 $s$。

输出格式

对于每组测试用例，输出两个整数，表示经过任意次操作后，最终字符串中 $1$ 的最小和最大个数。

输入输出样例

输入 #1
4
3
111
6
011011
7
1011101
9
100101101
输出 #1
2 3
3 5
4 7
5 7
C++ 编辑器
输入
输出