Codeforces Round 887 (Div. 1) |
---|
Закончено |
Ntarsis получил набор $$$S$$$, изначально содержащий целые числа $$$1, 2, 3, \ldots, 10^{1000}$$$ в отсортированном порядке. Каждый день он будет одновременно удалять $$$a_1$$$-е, $$$a_2$$$-е, $$$\ldots$$$, $$$a_n$$$-е наименьшие числа в $$$S$$$.
Какое наименьшее число останется в $$$S$$$ после $$$k$$$ дней?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.
Гарантируется, что:
Для каждого набора входных данных выведите целое число, которое является наименьшим элементом в $$$S$$$ после $$$k$$$ дней.
75 11 2 4 5 65 31 3 5 6 74 10002 3 4 59 14341 4 7 9 12 15 17 18 2010 41 3 5 7 9 11 13 15 17 1910 61 4 7 10 13 16 19 22 25 2810 1500001 3 4 5 10 11 12 13 14 15
3 9 1 12874 16 18 1499986
В первом наборе входных данных каждый день удаляется $$$1$$$-й, $$$2$$$-й, $$$4$$$-й, $$$5$$$-й и $$$6$$$-й наименьшие элементы из $$$S$$$. Таким образом, после первого дня $$$S$$$ станет равным $$$\require{cancel}$$$ $$$\{\cancel 1, \cancel 2, 3, \cancel 4, \cancel 5, \cancel 6, 7, 8, 9, \ldots\} = \{3, 7, 8, 9, \ldots\}$$$. Наименьшим элементом является $$$3$$$.
Во втором наборе каждый день удаляется $$$1$$$-й, $$$3$$$-й, $$$5$$$-й, $$$6$$$-й и $$$7$$$-й наименьшие элементы из $$$S$$$. $$$S$$$ будет изменяться следующим образом:
День | $$$S$$$ до | $$$S$$$ после | |
1 | $$$\{\cancel 1, 2, \cancel 3, 4, \cancel 5, \cancel 6, \cancel 7, 8, 9, 10, \ldots \}$$$ | $$$\to$$$ | $$$\{2, 4, 8, 9, 10, \ldots\}$$$ |
2 | $$$\{\cancel 2, 4, \cancel 8, 9, \cancel{10}, \cancel{11}, \cancel{12}, 13, 14, 15, \ldots\}$$$ | $$$\to$$$ | $$$\{4, 9, 13, 14, 15, \ldots\}$$$ |
3 | $$$\{\cancel 4, 9, \cancel{13}, 14, \cancel{15}, \cancel{16}, \cancel{17}, 18, 19, 20, \ldots\}$$$ | $$$\to$$$ | $$$\{9, 14, 18, 19, 20, \ldots\}$$$ |
Наименьшим элементом, оставшимся после $$$k = 3$$$ дней, является $$$9$$$.
Название |
---|