Codeforces Round 975 (Div. 1) |
---|
Закончено |
У вас есть несколько карт. На каждой карте написано целое число от $$$1$$$ до $$$n$$$: в частности, для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ у вас есть $$$a_i$$$ карт, на которых написано число $$$i$$$.
Также существует магазин, в котором продается неограниченное количество карт каждого типа. У вас есть $$$k$$$ монет, поэтому вы можете купить в общей сложности не более $$$k$$$ новых карт, и карты, которые вы покупаете, могут содержать любые целые числа от $$$\mathbf{1}$$$ до $$$\mathbf{n}$$$, включительно.
После покупки новых карт вы должны разбить все свои карты на колоды согласно следующим правилам:
Найдите максимально возможный размер колоды после покупки карт и их оптимального разбиения.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^{16}$$$) — количество различных типов карт и количество монет.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{10}$$$, $$$\sum a_i \geq 1$$$) — количество карт типа $$$i$$$, имеющихся у вас в начале, для каждого $$$1 \leq i \leq n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимально возможный размер колоды при оптимальных действиях.
93 13 2 25 42 6 1 2 42 1001410065408 1000000000010 87 4 6 6 9 3 10 2 8 72 122 22 700 11 013 02 1 23 10 3 3
2 3 1 7 2 2 1 1 2
В первом наборе входных данных вы можете купить одну карту с числом $$$1$$$, и ваш набор карт станет таким: $$$[1, 1, 1, 1, 2, 2, 3, 3]$$$. Вы можете разбить их на колоды $$$[1, 2], [1, 2], [1, 3], [1, 3]$$$. Они все имеют размер $$$2$$$, и все содержат разные значения. Можно показать, что невозможно получить разбиение с колодами размером больше $$$2$$$, поэтому ответ — $$$2$$$.
Во втором наборе входных данных вы можете купить две карты с числом $$$1$$$ и одну карту с числом $$$3$$$, и ваш набор карт станет таким: $$$[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5]$$$. Его можно разбить на колоды $$$[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5]$$$. Можно показать, что нельзя получить разбиение с колодами размером больше $$$3$$$, поэтому ответ — $$$3$$$.
Название |
---|