简单版本和困难版本之间的唯一区别在于限制。在此版本中,限制较低。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
Koa 考拉在海滩!
海滩由(从左到右)海岸、$$$n+1$$$ 米长的大海和距离海岸 $$$n+1$$$ 米的岛屿组成。
她测量了距离海岸 $$$1, 2, \dots, n$$$ 米处的海水深度,并将它们保存在数组 $$$d$$$ 中。 $$$d_i$$$ 表示 $$$1 \le i \le n$$$ 距离海岸 $$$i$$$ 米处的海水深度。
与任何海滩一样,这个海滩也有潮汐,潮汐强度由参数 $$$k$$$ 测量,并通过以下方式影响从 $$$t=0$$$ 时刻开始的所有深度:
- 总共 $$$k$$$ 秒,潮汐每秒都会使所有深度增加 $$$1$$$。
- 然后,在总共 $$$k$$$ 秒内,潮汐每秒都会使所有深度减少 $$$1$$$。
- 这个过程一次又一次地重复(即深度增加 $$$k$$$ 秒,然后减少 $$$k$$$ 秒,依此类推...)。正式地,让我们定义 $$$0$$$ 索引数组 $$$p = [0, 1, 2, \ldots, k - 2, k - 1, k, k - 1, k - 2, \ldots, 2, 1]$$$ 长度为 $$$2k$$$。在时间 $$$t$$$ ($$$0 \le t$$$) 距离海岸 $$$i$$$ 米处的深度等于 $$$d_i + p[t \bmod 2k]$$$ ($$$t \bmod 2k$$$ 表示 $$$t$$$ 除以 $$$2k$$$ 的余数)。请注意,更改会在每一秒后立即发生,请参阅注释以更好地理解。
在$$$t=0$$$时刻,Koa 站在岸边,想要上岛。假设在某个时间 $$$t$$$ ($$$0 \le t$$$) 她距离海岸 $$$x$$$ ($$$0 \le x \le n$$$) 米:
- 一秒钟内 Koa 可以游离海岸 $$$1$$$ 米远($$$x$$$ 更改为 $$$x+1$$$)或根本不游泳($$$x$$$ 保持不变),在这两种情况下 $$$t$$$ 更改为 $$$t+1$$$。
- 由于 Koa 的游泳能力很差,她所在点的海水深度在整数时间点不能超过 $$$l$$$(否则她会被淹死)。更正式地说,如果 Koa 目前 $$$t$$$ 距离海岸 $$$x$$$ ($$$1 \le x \le n$$$) 米(对于某个整数 $$$t\ge 0$$$),则此时的海水深度 — $$$d_x + p[t \bmod 2k]$$$ — 不能超过 $$$l$$$。换句话说,$$$d_x + p[t \bmod 2k] \le l$$$ 必须始终成立。
- 一旦 Koa 到达距离海岸 $$$n+1$$$ 米的岛屿,她就会停下来休息。请注意,Koa 游泳时潮汐不会对她产生影响(即,她在游泳时不会被淹死)。请注意,Koa 可以选择在岸上停留多久,只要她需要,海岸或岛屿都不会受到潮汐的影响(它们是坚实的地面,她不会在那里淹死)。
Koa 想知道她是否可以从海岸到岛上。帮助她!
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$l$$$ ($$$1 \le n \le 100; 1 \le k \le 100; 1 \le l \le 100$$$) — 测量的海 Koa 米数以及参数 $$$k$$$ 和 $$$l$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \le d_i \le 100$$$) — 测量的科阿海每米的深度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$100$$$。
输出
对于每个测试用例:
如果 Koa 可以从海岸到达岛屿,则打印“是”,否则打印“否”。
您可以以任何大小写形式打印每个字母(大写或小写)。
示例
输入 #1
7 2 1 1 1 0 5 2 3 1 2 3 2 2 4 3 4 0 2 4 3 2 3 5 3 0 7 2 3 3 0 2 1 3 0 1 7 1 4 4 4 3 0 2 4 2 5 2 3 1 2 3 2 2
输出 #1
Yes No Yes Yes Yes No No
注意
下面的 $$$s$$$ 表示海岸,$$$i$$$ 表示岛屿,$$$x$$$ 表示从 Koa 到海岸的距离,下划线表示 Koa 的位置,下面数组中的值表示受潮汐影响的当前深度,距离海岸 $$$1, 2, \dots, n$$$ 米。
在测试用例 $$$1$$$ 中,我们有 $$$n = 2, k = 1, l = 1, p = [ 0, 1 ]$$$。
Koa 想要从海岸($$$x = 0$$$)到岛屿($$$x = 3$$$)。让我们描述一个可能的解决方案:
- 最初在 $$$t = 0$$$ 时,海滩如下所示:$$$[\underline{s}, 1, 0, i]$$$。
- 在 $$$t = 0$$$ 处,如果 Koa 决定游到 $$$x = 1$$$,海滩看起来会是这样的: $$$[s, \underline{2}, 1, i]$$$ 在 $$$t = 1$$$ 处,因为 $$$2 > 1$$$ 她会淹死。因此,Koa 会等待 $$$1$$$ 秒,而海滩在 $$$t = 1$$$ 处看起来像 $$$[\underline{s}, 2, 1, i]$$$。
- 在 $$$t = 1$$$ 处,Koa 游到 $$$x = 1$$$,海滩看起来像 $$$[s, \underline{1}, 0, i]$$$ 在 $$$t = 2$$$ 处。相思树不会被淹死,因为 $$$1 \le 1$$$。
- 在 $$$t = 2$$$ 处,Koa 游至 $$$x = 2$$$,海滩看起来像 $$$[s, 2, \underline{1}, i]$$$ 在 $$$t = 3$$$ 处。相思树不会被淹死,因为 $$$1 \le 1$$$。
- 在 $$$t = 3$$$ 处,Koa 游到 $$$x = 3$$$,海滩看起来像 $$$[s, 1, 0, \underline{i}]$$$ 在 $$$t = 4$$$ 处。
- 在 $$$t = 4$$$ Koa 的位置为 $$$x = 3$$$,她成功了!
我们可以证明,在测试用例中 $$$2$$$ Koa 无法到达岛屿。