← 返回题目列表

Codeforces · 1496/B

B. 麦克斯和墨西哥

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

给定一个多重集 $$$S$$$,最初由 $$$n$$$ 不同的非负整数组成。多重集是一个可以多次包含某些元素的集合。

您将执行以下操作 $$$k$$$ 次:

- 将元素 $$$\lceil\frac{a+b}{2}\rceil$$$ (向上舍入)添加到 $$$S$$$ 中,其中 $$$a = \operatorname{mex}(S)$$$ 和 $$$b = \max(S)$$$。如果该数字已在集合中,则会再次添加。

这里多重集的 $$$\operatorname{max}$$$ 表示多重集中的最大整数,多重集的 $$$\operatorname{mex}$$$ 表示多重集中不存在的最小非负整数。例如:

- $$$\operatorname{mex}(\{1,4,0,2\})=3$$$;
- $$$\operatorname{mex}(\{2,5,1\})=0$$$。

您的任务是在完成 $$$k$$$ 操作后计算 $$$S$$$ 中不同元素的数量。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1\le n\le 10^5$$$, $$$0\le k\le 10^9$$$) - 多重集 $$$S$$$ 的初始大小以及需要执行的操作数量。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_i\le 10^9$$$) - 初始多重集中的数字。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,在完成 $$$k$$$ 操作后打印 $$$S$$$ 中不同元素的数量。

示例

输入 #1

5
4 1
0 1 3 4
3 1
0 1 4
3 0
0 1 4
3 2
0 1 2
3 2
1 2 3

输出 #1

4
4
3
5
3

注意

在第一个测试用例中,$$$S=\{0,1,3,4\}$$$、$$$a=\operatorname{mex}(S)=2$$$、$$$b=\max(S)=4$$$、$$$\lceil\frac{a+b}{2}\rceil=3$$$。所以$$$3$$$被添加到$$$S$$$中,$$$S$$$变成$$$\{0,1,3,3,4\}$$$。答案是$$$4$$$。

在第二个测试用例中,$$$S=\{0,1,4\}$$$、$$$a=\operatorname{mex}(S)=2$$$、$$$b=\max(S)=4$$$、$$$\lceil\frac{a+b}{2}\rceil=3$$$。所以$$$3$$$被添加到$$$S$$$中,$$$S$$$变成$$$\{0,1,3,4\}$$$。答案是$$$4$$$。