← 返回题目列表

Codeforces · 2117/A

A. 误报

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

Yousef 位于一条长长的走廊入口处,走廊里有一排 $$$n$$$ 扇门,编号从 $$$1$$$ 到 $$$n$$$。他需要按编号顺序穿过从 $$$1$$$ 到 $$$n$$$ 的所有门并到达出口(经过门 $$$n$$$)。

每扇门都可以打开或关闭。如果门打开,Yousef 将在 $$$1$$$ 秒内穿过它。如果门关着,尤瑟夫就无法通过。

然而,Yousef 有一个特殊的按钮,他可以使用 最多一次 随时。此按钮使所有关闭的门打开 $$$x$$$ 秒。

你的任务是确定 Yousef 是否可以通过所有门(如果他最多可以使用一次按钮)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n, x$$$ ($$$1 \le n, x \le 10$$$) — 分别是门的数量和按钮的秒数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, ..., a_n$$$ ($$$a_i \in \{0, 1\}$$$) — 每个门的状态。打开的门表示为 '0',而关闭的门由 '1'.

保证每个测试用例至少包含一扇关闭的门。

输出

对于每个测试用例,输出“是“如果 Yousef 能够到达出口,并且”NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

7
4 2
0 1 1 0
6 3
1 0 1 1 0 0
8 8
1 1 1 0 0 1 1 1
1 2
1
5 1
1 0 1 0 1
7 4
0 0 0 1 1 0 1
10 3
0 1 0 0 1 0 0 1 0 0

输出
复制

YES
NO
YES
YES
NO
YES
NO

注意

第一个测试用例中,最优方式如下:

  • 在 $$$0$$$ 时间,门打开,因此 Yousef 通过。
  • 在时间$$$1$$$,门已关闭,Yousef 现在可以使用按钮并穿过门。
  • 在$$$2$$$时间,该按钮的效果仍然有效,因此 Yousef 仍然可以通过。
  • 在时间$$$3$$$,按钮的效果已完成,但门是打开的。尤瑟夫经过并到达出口。

在第二个测试用例中,Yousef 有一个 3 秒按钮,但他至少需要一个 4 秒按钮才能到达出口。因此,答案是 NO.

在第三个测试用例中,Yousef 可以在开始移动之前打开按钮。所有的门都会保持打开状态,直到他到达出口。