P9317 [EGOI 2022] SubsetMex / Subset mex

Day 1 Problem A. The statement is translated from [EGOI2022 subsetmex](https://stats.egoi.org/media/task_description/2022_subsetmex_en.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

A *multiset* is a set in which elements may appear multiple times. For example, $\{0,0,1,2,2,5,5,5,8\}$ is a multiset. You are given a multiset $S$ with values in $\N$, and a target natural number $n$ ($n\notin S$). Your goal is to make $n\in S$ by repeatedly performing the following operation some number of times: 1. Choose a (possibly empty) subset $T\subseteq S$, where $T$ contains no duplicate elements. 2. Delete the elements of $T$ from $S$. (If an element appears multiple times, remove only one copy.) 3. Insert $\operatorname{mex}(T)$ into $S$, where $\operatorname{mex}(T)$ is the smallest natural number that is not in $T$. $\operatorname{mex}$ stands for “minimum excluded value”. You need to find the minimum number of operations needed to make $n\in S$. Since $|S|$ can be very large, it is given as a list of length $n$, $(f_0,\ldots f_{n-1})$, where $f_i$ denotes how many times $i$ appears in $S$. (Recall that $n$ is the element we want to insert into $S$.)

The first line contains an integer $t$, the number of test cases. Then each test case is described in two lines: - The first line of each test case contains an integer $n$, the element to be inserted into $S$. - The second line contains $n$ integers $f_0,f_1,\ldots,f_{n-1}$, describing the multiset $S$ as above.

For each test case, output one line containing one integer, the minimum number of operations.

**Explanation for Sample $1$.** Initially, $S=\{1,1,1,3,3,3\}$, and the goal is to make $4\in S$. We can do the following operations: 1. Let $T=\varnothing$, then $S=\{0,1,1,1,3,3,3\}$. 2. Let $T=\{0,1,3\}$, then $S=\{1,1,2,3,3\}$. 3. Let $T=\{1\}$, then $S=\{0,1,2,3,3\}$. 4. Let $T=\{0,1,2,3\}$, then $S=\{3,4\}$. --- **Constraints** For all testdata, $1\le t\le 200$, $1\le n\le 50$, $0\le f_i\le 10^{16}$. - Subtask 1 ($5$ points): $n\le 2$. - Subtask 2 ($17$ points): $n\le 20$. - Subtask 3 ($7$ points): $f_i=0$. - Subtask 4 ($9$ points): $f_i\le 1$. - Subtask 5 ($20$ points): $f_i\le 2\times 10^3$. - Subtask 6 ($9$ points): $f_0\le 10^{16}$ and $\forall j\ne 0,f_j=0$. - Subtask 7 ($10$ points): $\exists i,f_i\le 10^{16}$ and $\forall j\ne i,f_j=0$. - Subtask 8 ($23$ points): No special constraints. # Input Format # Output Format Translated by ChatGPT 5