P3881 [JLOI2008] CODES

Given $n$ $\texttt{01}$ code strings $S_1, S_2, \dots, S_n$, your task is to find a code string $T$ such that it can be decomposed in at least two different ways as a concatenation of the $S_i$. For example: Given $5$ $\texttt{01}$ code strings: $S_1=\texttt{0110}, S_2=\texttt{00}, S_3=\texttt{111}, S_4=\texttt{001100}, S_5=\texttt{110}$. Then one valid code string $T$ is: \texttt{001100110}, which has the following two decompositions: \texttt{00}+\texttt{110}+\texttt{0110} $(S_2+S_5+S_1)$ or \texttt{001100}+\texttt{110} $(S_4+S_5)$. But 0110110 does not meet the requirement; it has only one decomposition \texttt{0110}+\texttt{110} $(S_1+S_5)$. You must find the shortest valid code string $T$. If there are multiple shortest valid code strings $T$, output the lexicographically smallest one.

The first line contains an integer $n$, the number of $\texttt{01}$ code strings. Each of the next $n$ lines contains one $\texttt{01}$ code string of length at most $20$.

Output two lines. The first line is the length of the required code string $T$. The second line is the code string $T$. For all the testdata, a solution always exists.

- $n \le 20$. Translated by ChatGPT 5