这是问题的简单版本。两个版本之间的唯一区别是对 $$$t$$$、$$$m$$$ 和 $$$m$$$ 总和的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
Alice 和 Bob 在大小为 $$$n$$$ 的数组 $$$a$$$ 上玩另一个游戏。 Alice 从一个空数组 $$$c$$$ 开始。两名玩家轮流玩,爱丽丝先开始。
轮到 Alice 时,她从 $$$a$$$ 中选择一个元素,将该元素附加到 $$$c$$$,然后从 $$$a$$$ 中删除它。
轮到 Bob 时,他从 $$$a$$$ 中最多选取 $$$k$$$ 个元素,然后从 $$$a$$$ 中删除它。
当数组 $$$a$$$ 为空时游戏结束。 Alice 的分数被定义为 $$$c$$$ 的 MEX$$$^\dagger$$$。爱丽丝想要最大化她的分数,而鲍勃想要最小化它。如果两个玩家都发挥最佳,求爱丽丝的最终得分。
数组将以压缩格式给出。我们将给出它们的频率,而不是给出数组中存在的元素。形式上,您将得到数组中的最大元素 $$$m$$$,然后是 $$$m + 1$$$ 整数 $$$f_0, f_1, \ldots, f_m$$$,其中 $$$f_i$$$ 表示 $$$i$$$ 在数组 $$$a$$$ 中出现的次数。
$$$^\dagger$$$ 整数数组的 $$$\operatorname{MEX}$$$ (最小排除数)被定义为数组中未出现的最小非负整数。例如:
- $$$[2,2,1]$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
- $$$[3,1,0,1]$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$[0,3,1,2]$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于数组,但 $$$4$$$ 不属于该数组。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$m$$$ 和 $$$k$$$ ($$$1 \le m \le 50, 1 \le k \le 10^9$$$)。
第二行包含 $$$m + 1$$$ 整数 $$$f_0, f_1, \ldots, f_m$$$ ($$$1 \le f_i \le 10^9$$$)。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,如果两个玩家都发挥最佳,则找到 Alice 的分数。
示例
输入 #1
5 1 4 4 5 2 1000000000 1000000000 1000000000 1000000000 3 2 2 3 100 1 1 1 2 2 3 1 1 1 1 1
输出 #1
2 1 3 2 1
注意
在第一个测试用例中,数组 $$$a$$$ 是 $$$[0, 0, 0, 0, 1, 1, 1, 1, 1]$$$。得分为 $$$2$$$ 的可能游戏如下:
1. Alice 选择元素 $$$0$$$。此举后,$$$a = [0, 0, 0, 1, 1, 1, 1, 1]$$$ 和 $$$c=[0]$$$。
2. Bob 选择删除 $$$3$$$ 元素 $$$0$$$、$$$0$$$ 和 $$$1$$$。此举后,$$$a = [0, 1, 1, 1, 1]$$$ 和 $$$c=[0]$$$。
3. Alice 选择元素 $$$1$$$。在此移动之后,$$$a = [0,1,1,1]$$$ 和 $$$c=[0,1]$$$。
4. Bob 删除 $$$4$$$ 剩余元素 $$$0$$$、$$$1$$$、$$$1$$$ 和 $$$1$$$。在此移动之后,$$$a=[\,]$$$ 和 $$$c=[0,1]$$$。
最后,$$$c=[0,1]$$$,其 MEX 为 $$$2$$$。请注意,这是一个示例游戏,并不一定代表双方玩家的最佳策略。
在第二个测试用例中,Alice 在第一轮中可以选择 $$$0$$$,保证她的分数至少为 $$$1$$$。而Bob可以在第一回合中删除元素$$$1$$$的所有副本,从而保证Alice的得分不会超过$$$1$$$。因此,如果两个玩家都发挥最佳,Alice 的得分为 $$$1$$$。