← 返回题目列表

Codeforces · 1852/A

A. Ntarsis 套装

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

Ntarsis 被赋予了一个集合 $$$S$$$,最初包含按排序顺序的整数 $$$1, 2, 3, \ldots, 10^{1000}$$$。每天,他都会同时删除$$$S$$$中第$$$a_1$$$、第$$$a_2$$$、$$$\ldots$$$、$$$a_n$$$个最小的数字。

$$$k$$$ 天后 $$$S$$$ 中的最小元素是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行由两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n,k \leq 2 \cdot 10^5$$$) 组成 - $$$a$$$ 的长度和天数。

每个测试用例的以下行由 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) 组成 - 数组 $$$a$$$ 的元素。

保证:

- 所有测试用例的 $$$n$$$ 总和不会超过 $$$2 \cdot 10^5$$$;
- 所有测试用例的 $$$k$$$ 总和不会超过 $$$2 \cdot 10^5$$$;
- 对于所有测试用例,$$$a_1 < a_2 < \cdots < a_n$$$。

输出

对于每个测试用例,打印一个整数,该整数是 $$$k$$$ 天后 $$$S$$$ 中的最小元素。

示例

输入 #1

7
5 1
1 2 4 5 6
5 3
1 3 5 6 7
4 1000
2 3 4 5
9 1434
1 4 7 9 12 15 17 18 20
10 4
1 3 5 7 9 11 13 15 17 19
10 6
1 4 7 10 13 16 19 22 25 28
10 150000
1 3 4 5 10 11 12 13 14 15

输出 #1

3
9
1
12874
16
18
1499986

注意

对于第一个测试用例,每天需要从 $$$S$$$ 中删除第 $$$1$$$-st、$$$2$$$-nd、$$$4$$$-th、$$$5$$$-th 和 $$$6$$$-th 最小元素。所以第一天之后,$$$S$$$ 将变成 $$$\require{cancel}$$$ $$$\{\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots\} = \{3, 7, 8, 9, \ldots\}$$$。最小的元素是$$$3$$$。

对于第二种情况,每天需要从 $$$S$$$ 中删除第 $$$1$$$-st、$$$3$$$-rd、$$$5$$$-th、$$$6$$$-th 和 $$$7$$$-th 最小元素。 $$$S$$$ 将更改如下:

天$$$S$$$之前$$$S$$$之后1$$$\{\取消1, 2, \取消3, 4, \取消5, \取消6, \取消7, 8, 9, 10, \ldots \}$$$$$$\到$$$$$$\{2, 4, 8, 9, 10, \ldots\}$$$2$$$\{\取消 2, 4, \取消 8, 9, \取消{10}, \取消{11}, \取消{12}, 13, 14, 15, \ldots\}$$$$$$\到$$$$$$\{4, 9, 13, 14, 15, \ldots\}$$$3$$$\{\取消 4, 9, \取消{13}, 14, \取消{15}, \取消{16}, \取消{17}, 18, 19, 20, \ldots\}$$$$$$\到$$$$$$\{9, 14, 18, 19, 20, \l点\}$$$

$$$k = 3$$$ 天后剩下的最小元素是 $$$9$$$。