题目描述
给定长度为 k 的序列 {ak}。我们将以下操作称为一次迭代:
- 找到当前序列中未被删去的最小的元素 am,若有多个最小的元素,随机选取其一;
- 令 am←am+1,而对于其他未被删去的 i=m,ai←ai−1;
- 若 ∣a∣>3,从后向前删去所有值为 0 的元素,直到 ∣a∣≤3。删去元素不改变其他元素序号。
其中 ∣a∣ 表示序列中未被删去的元素数量。
如此不断迭代,直到仅有一个 ap>0。给定 x,试问 x 是否一定为最后的 p。
输入格式
本题在单个测试点中有多组数据。
输入共 2×T+1 行。
第 1 行 1 个整数,表示单个测试点中的数据组数 T。
接下来,对于每组数据,输入共 2 行:
- 第 1 行 2 个整数,分别表示序列长度 k 和询问的序号 x;
- 第 2 行 k 个整数,分别表示每个 ai。
输出格式
输出共 T 行。
对于每组数据,输出共 1 行 1 个字符串,若一定为最后的 p 则输出 Yes,反之输出 No。
输入输出样例
3
4 3
1 2 2 1
3 1
3 2 2
4 4
5 3 3 2
No
Yes
Yes
提示
【样例 1 解释】
在第 3 组数据中,可以证明,无论如何都有 p=4。如下所示为一种可能的情况,在第 2 次迭代时选择第 a3 加一,而在第 5 次迭代时选择第 a2 加一:
迭代次数 |
迭代后序列 |
未删除序号 |
1 |
{4,2,2,3} |
{1,2,3,4} |
2 |
{3,1,3,2} |
3 |
{2,2,2,1} |
4 |
{1,1,1,2} |
5 |
{0,2,0,1} |
6 |
{0,2,1} |
{1,2,4} |
7 |
{1,1,0} |
8 |
{0,0,1} |
【数据范围】
本题开启捆绑测试。
对于 100% 的数据,1≤T≤10,3≤k≤106,1≤x≤k,1≤ai≤1018。
Subtask |
k≤ |
ai≤ |
Score |
1 |
10 |
100 |
10 |
2 |
103 |
103 |
15 |
3 |
1018 |
4 |
5×104 |
20 |
5 |
106 |
40 |