← 返回题目列表

Codeforces · 1244/B

B. 房间和楼梯

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

尼古拉住在一栋两层楼的房子里。每层有$$$n$$$个房间,排成一排,从左到右编号。所以每个房间都可以用楼层号和该楼层的房间号来表示(房间号是$$$1$$$到$$$n$$$之间的整数)。

如果尼古拉当前在某个房间,他可以移动到任何相邻的房间(如果存在)。每层楼上编号为 $$$i$$$ 和 $$$i+1$$$ 的房间都是相邻的,对于所有 $$$1 \leq i \leq n - 1$$$。还可能存在连接不同楼层的具有相同编号的两个房间的楼梯。如果有一个楼梯连接一楼的$$$x$$$房间和二楼的$$$x$$$房间,那么Nikolay可以使用它从一个房间移动到另一个房间。

该图展示了一座 $$$n = 4$$$ 的房子。一楼$$$2$$$房间和二楼$$$2$$$房间之间有一个楼梯,一楼$$$4$$$房间和二楼$$$4$$$房间之间还有一个楼梯。箭头表示尼古拉可以移动的可能方向。该图片对应于输入中的字符串“0101”。

尼古拉想要穿过他房子里的一些房间。为此,他首先选择他开始的任何房间。然后尼古拉根据上述规则在房间之间移动。尼古拉从来不会两次访问同一个房间(他不会进入他已经去过的房间)。

计算尼古拉在旅行期间可以访问的最大房间数,如果:

- 他可以在他选择的任何楼层的任何房间开始,
- 他不会两次访问同一个房间。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 输入中测试用例的数量。然后是测试用例。每个测试用例由两行组成。

第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 1\,000)$$$ — 每层的房间数。

第二行包含一个由 $$$n$$$ 个字符组成的字符串,每个字符要么是“0”,要么是“1”。如果第 $$$i$$$ 个字符是“1”,则一楼 $$$i$$$ 房间和二楼 $$$i$$$ 房间之间有一个楼梯。如果第 $$$i$$$ 个字符是“0”,则一楼 $$$i$$$ 房间和二楼 $$$i$$$ 房间之间没有楼梯。

在 hacks 中,只允许在输入中使用一个测试用例,因此应该满足 $$$t = 1$$$ 。

输出

对于每个测试用例,打印一个整数 - Nikolay 在他的旅行期间可以访问的最大房间数,如果他可以从任何楼层的任何房间开始,并且他不会访问同一个房间两次。

示例

输入 #1

4
5
00100
8
00000000
5
11111
3
110

输出 #1

6
8
10
6

注意

在第一个测试用例中,尼古拉可能会在一楼的第一个房间开始。然后他搬到了一楼的第二个房间,然后——一楼的第三个房间。然后他通过楼梯来到了二楼的第三个房间。然后他去了二楼第四个房间,然后——二楼第五个房间。因此,尼古拉参观了 $$$6$$$ 房间。

第二个测试用例中没有楼梯,因此 Nikolay 只能访问同一楼层的所有房间(如果他从最左边或最右边的房间开始)。

在第三个测试用例中,可以访问所有房间:一楼,第一个房间 $$$\rightarrow$$$ 二楼,第一个房间 $$$\rightarrow$$$ 二楼,第二个房间 $$$\rightarrow$$$ 一楼,第二个房间 $$$\rightarrow$$$ 一楼,第三个房间 $$$\rightarrow$$$ 二楼,第三个房间 $$$\rightarrow$$$ 二楼,第四个房间$$$\rightarrow$$$ 一楼,第四个房间 $$$\rightarrow$$$ 一楼,第五个房间 $$$\rightarrow$$$ 二楼,第五个房间。

在第四个测试用例中,也可以访问所有房间:二楼,第三个房间 $$$\rightarrow$$$ 二楼,第二个房间 $$$\rightarrow$$$ 二楼,第一个房间 $$$\rightarrow$$$ 一楼,第一个房间 $$$\rightarrow$$$ 一楼,第二个房间 $$$\rightarrow$$$ 一楼,第三个房间。