Назовём разбиением множества $$$B$$$ набор множеств $$$s_1, s_2,\ldots, s_k$$$, такой что каждый элемент встречается одинаковое количество раз в $$$B$$$ и суммарно в множествах $$$s_1,s_2,\ldots,s_k$$$.
Например, некоторыми разбиениями множества $$$\{1,2,3,3\}$$$ являются $$$\{1,3\}+\{2,3\}, \{1,2,3,3\}$$$ и $$$\{2\}+\{1,3\}+\{3\}$$$, но не $$$\{1,2\}+\{3\}$$$.
Разбиение называется корректным, если $$$\operatorname{mex}$$$$$$^{\text{∗}}$$$ всех множеств в разбиении одинаков. Оценка корректного разбиения — это $$$\operatorname{mex}$$$ любого множества в разбиении.
Вам дано множество $$$A$$$ размера $$$n$$$. Найдите минимальную оценку среди всех корректных разбиений $$$A$$$.
$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 100$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$A_1, A_2, \ldots, A_n$$$, обозначающих элементы $$$A$$$ ($$$0 \leq A_i \leq 100$$$).
Не гарантируется, что элементы даны в неубывающем порядке.
Для каждого набора входных данных выведите минимальную оценку среди всех корректных разбиений.
230 0 021 2
10
В первом наборе входных данных минимальная оценка $$$1$$$ может быть получена с помощью разбиения $$$\{0\}+\{0\}+\{0\}$$$. Разбиение является корректным, потому что у каждого множества $$$\operatorname{mex}$$$ равен $$$1$$$, что, следовательно, является оценкой разбиения.
Во втором наборе входных данных мы можем использовать $$$\{1,2\}$$$ как единственное множество в разбиении, и оно имеет $$$\operatorname{mex} 0$$$.
| Codeforces Round 1058 (Div. 2) |
|---|
| Закончено |
