\begin{tutorial}{Hidden Digits}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Михаил Дворкин\\
         Разработка: & Николай Будин\\
     \end{tabular}
}

Давайте реализуем рекурсивную функцию \t{solve(a, f)}, которая принимает массив двоичных масок $a_0$, $a_1$, \dots $a_{k - 1}$ и находит минимальное $x$ такое, что в $x$ встречаются все цифры из $a_0$, в $(x + 1)$ встречаются все цифры из $a_1$, и т.д. Дополнительно эта функция будет принимать флаг $f$, обозначающий, может ли $x$ равняться $0$, или оно должно быть строго положительным.

Теперь рассмотрим три случая для функции \t{solve}:
\begin{itemize}
\item Если $|a| = 1$. Тогда нам нужно просто собрать минимальное число, которое содержит все цифры из $a_0$ и удовлетворяет флагу $f$. В большинстве случаев достаточно взять цифры из $a_0$ в возрастающем порядке, и если на первом месте оказался $0$, то поменять местами первую и вторую цифры. Однако, есть крайние случаи, которые нужно аккуратно разобрать: если $a_0$ пусто; если $x$ не может быть $0$; если $a_0$ содержит только $0$.
\item Если $|a| = 2$. Тогда есть два интересных варианта, как могут выглядеть $x$ и $x + 1$:
\begin{enumerate}
\item $x = \overline{\dots d}$, $x + 1 = \overline{\dots (d + 1)}$, $d < 9$. То есть, $x$ и $x + 1$ имеют одинаковый префикс, и разные цифры на конце. Переберем $d$, вычеркнем $d$ из $a_0$, вычеркнем $d + 1$ из $a_1$, сделаем $b = a_0 | a_1$, и найдем минимальное число,  содержащее все цифры из $b$.
\item $x = \overline{\dots d 9}$, $x + 1 = \overline{\dots (d + 1) 0}$, $d < 9$. Снова переберем $d$.
\end{enumerate}
\item Если $|a| > 2$. Тогда переберем $x \bmod 10$, то есть последнюю цифру первого числа. В результате, мы узнаем последние цифры всех чисел. Вычеркнем их из масок. Теперь отбросим у каждого числа последнюю цифру, то есть нацело поделим все числа на $10$. В результате у нас будут отрезки подряд идущих одинаковых чисел. Объединим числа внутри такого отрезка в одно, при этом множества необходимых цифр объединятся. Рекурсивно вызовем \t{solve} от нового множества масок, чтобы найти минимальное подходящее значение $\lfloor\frac{x}{10}\rfloor$.
\end{itemize}

Пусть функция \t{solve} при $|a| = n$ работает за $T(n)$. Тогда $T(n) = 10 \cdot T(n / 10) + O(n)$. Поэтому, $T(n) = O(n \log n)$.

Чтобы решить задачу, нужно запустить \t{solve} с $a_i = \{d_i\}$.

%Let's implement a recursive function \t{calc(a, fl)}, that will take an array of binary masks $a_0$, $a_1$, \dots $a_{k - 1}$. And find the minimum possible $x$, such that $x$ contains every digit from the set $a_0$ (at least once for every digit from the set), $x + 1$ contains all the digits from the $a_1$, and so on. Additionally, \t{calc} takes argument $fl$, which means if $x$ can be $0$ or if it should be strictly positive.

%Now we should consider three cases:
%\begin{itemize}
%\item $|a| = 1$. Then you should take digits from the $a_0$ in the increasing order, if it starts with $0$, then swap it with the second digit. Some tricky cases, that you should handle: $x$ cannot be $0$; $a_0$ is empty; $a_0$ contains only $0$; $a_0$ contains $0$, and other digits.
%\item $|a| = 2$. Then there are two cases of how $x$ and $x + 1$ could look:
%\begin{enumerate}
%\item $x = \overline{\dots d}$, $x + 1 = \overline{\dots (d + 1)}$, $d < 9$. $d$ and $d + 1$ have the same prefix and different digits at the end. We can iterate over $d$, remove $d$ from $a_0$, remove $d + 1$ from $a_1$, make $b = a_0 | a_1$, and find the minimum number with digits from $b$.
%\item $x = \overline{\dots d 9}$, $x + 1 = \overline{\dots (d + 1) 0}$, $d < 9$. Again we can iterate over $d$.
%\end{enumerate}
%\item $|a| > 2$. Then let's iterate over all possible values of $x \bmod 10$. In other words, let's iterate over the last digit of the first number. When we've chosen that digit, we know the last digit for all the numbers. Now we can remove the corresponding digits from their masks. And after that, we can divide all numbers by $10$ (remove the last digit) and unite segments with the same value. And then call \t{calc} with the new compressed array of masks.
%\end{itemize}

%Let's say that function \t{calc} with $|a| = n$ works in $T(n)$. Then $T(n) = 10 \cdot T(n / 10) + O(n)$. So, $T(n) = O(n \log n)$.

%In order to solve the problem, we should call \t{calc} with $a_i = \{d_i\}$, $fl = false$.

\end{tutorial}
