← 返回题目列表

Codeforces · 1951/A

A. 双触发器

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

有 $$$n$$$ 编号为 $$$1$$$ 到 $$$n$$$ 的灯排成一排,最初是关闭的。您可以执行以下操作任意次数(可能为零):

- 选择当前关闭的两个不相邻的$$${}^\dagger$$$ 灯,然后将其打开。

确定是否可以达到配置$$$s$$$,其中$$$s_i = 1$$$表示第$$$i$$$灯打开,否则$$$s_i = 0$$$。

$$${}^\dagger$$$ 对于所有 $$$1 \le i < n$$$,只有灯 $$$i$$$ 和 $$$i + 1$$$ 是相邻的。请注意,当 $$$n \ne 2$$$ 时,灯 $$$n$$$ 和 $$$1$$$ 不相邻。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 灯的数量。

每个测试用例的第二行包含一个大小为 $$$n$$$ 的二进制字符串 $$$s$$$ — 最终所需的配置。

输出

对于每个测试用例,如果我们可以通过应用给定操作任意次数达到配置 $$$s$$$,则在一行上打印“YES”。否则,打印“NO”。

示例

输入 #1

5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111

输出 #1

YES
NO
YES
NO
YES

注意

在第一个测试用例中,操作顺序可能如下(请注意,最初 $$$s$$$ 全部为零): $$$\mathtt{0000000000} \to \mathtt{\color{red}{1}0000000\color{red}{1}0} \to \mathtt{1\color{red}{1}00000\color{red}{1}10} \到 \mathtt{110\color{red}{1}0\color{red}{1}0110}$$$。

在第三个测试用例中,我们不必执行任何操作。

在第四个测试用例中,我们无法进行任何操作,但我们需要打开第一盏灯。因此,不可能达到理想的状态。