No.3539 Parentheses Square
Problem Statement
If repeatedly deleting () contained as a (contiguous) substring of a string $X$ can turn $X$ into the empty string, and only in that case, $X$ is called a correct parenthesis sequence.
You are given a positive integer $N$ and $N$ strings of length $N$ consisting of ., (, ): $T_1, T_2, \cdots, T_N$.
Is it possible to replace every . contained in each of $T_1, T_2, \cdots, T_N$ with ( or ) to make $N$ pairwise distinct correct parenthesis sequences? If it is possible, construct one such way.
Formally, determine whether there exists an $N$-tuple $S_1, S_2, \cdots, S_N$ of strings of length $N$ satisfying all of the following conditions. If one exists, construct one.
- For each $i(1\leq i\leq N)$, $S_i$ is a correct parenthesis sequence
- If $T_{i, j}(1\leq i, j\leq N)$ is not
., then $S_{i, j}=T_{i, j}$ - For $1\leq i, j\leq N$, if $i\neq j$ then $S_i\neq S_j$
Here, for a string $X$, $X_i$ denotes the $i$-th character of $X$.
Input
$N$ $T_1$ $T_2$ $\vdots$ $T_N$
- $1\leq N\leq 200$
- $T_i$ is a string of length $N$ consisting of
.,(, and) - $N$ is an integer
Output
If a tuple $S_1, S_2, \cdots, S_N$ satisfying the conditions exists, output $N$ lines in the following format.
$S_1$ $S_2$ $\vdots$ $S_N$
If none exists, output -1.
$-1$
Print a newline at the end.
Sample
Sample 1
Input
8 (....... .......) .(...... ....)... ......() ........ ()...... .(....).
Output
((()())) ((())()) (()(())) (()()()) ((()))() (()())() ()((())) (((())))
There may be multiple solutions; the one shown here is just one example.
Sample 2
Input
2 .. ..
Output
-1
No $S_1, S_2$ satisfying the conditions exist. Therefore, output only -1.
Sample 3
Input
4 )))) (((( .... ....
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt
もの