A16693. MEX Partition
编程题
入门
知识点
题目描述
设多重集 $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}^*$ 均相同，则称这个划分为“合法”划分。合法划分的得分为划分中任意一个多重集的 $\operatorname{mex}$。
现给定一个大小为 $n$ 的多重集 $A$。请你求出所有合法划分的最小得分。
$^*$ 对于整数集 $c_1, c_2, \ldots, c_k$，$\operatorname{mex}$（最小未出现数）定义为不在集合 $c$ 中的最小非负整数 $x$。
例如，$\{1,2,3,3\}$ 的一些划分包括 $\{1,3\}+\{2,3\}$、$\{1,2,3,3\}$、以及 $\{2\}+\{1,3\}+\{3\}$，但是不包括 $\{1,2\}+\{3\}$。
如果所有多重集的 $\operatorname{mex}^*$ 均相同，则称这个划分为“合法”划分。合法划分的得分为划分中任意一个多重集的 $\operatorname{mex}$。
现给定一个大小为 $n$ 的多重集 $A$。请你求出所有合法划分的最小得分。
$^*$ 对于整数集 $c_1, c_2, \ldots, c_k$，$\operatorname{mex}$（最小未出现数）定义为不在集合 $c$ 中的最小非负整数 $x$。
输入格式
每个测试点包含多组测试数据。第一行包含测试组数 $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$）。
不保证输入的元素按递增顺序给出。
每组测试数据第一行包含整数 $n$（$1 \leq n \leq 100$）。
第二行包含 $n$ 个整数 $A_1, A_2, \ldots, A_n$，表示多重集 $A$ 的元素（$0 \leq A_i \leq 100$）。
不保证输入的元素按递增顺序给出。
输出格式
对于每组测试数据，输出所有合法划分的最小得分。
输入输出样例
输入 #1
2 3 0 0 0 2 1 2
输出 #1
1 0
说明/提示
在第一个测试用例中，最小得分 $1$ 可以通过划分 $\{0\}+\{0\}+\{0\}$ 得到。该划分是合法的，因为每个多重集的 $\operatorname{mex}$ 都为 $1$，这即为该划分的得分。
在第二个测试用例中，我们可以将 $\{1,2\}$ 作为分组中唯一的多重集，该多重集的 $\operatorname{mex}$ 为 $0$。
在第二个测试用例中，我们可以将 $\{1,2\}$ 作为分组中唯一的多重集，该多重集的 $\operatorname{mex}$ 为 $0$。