No.470 Inverse S+T Problem
ぴろず
kimiyukiProblem Statement
For strings $S,T$, let $S+T$ denote the concatenation of $S$ and $T$.
You are given $N$ strings $U_1,U_2,\dots,U_N$ of length $3$.
Find $2N$ pairwise distinct non-empty strings $S_1, S_2, \dots, S_N, T_1, T_2, \dots, T_N$ such that $S_i + T_i = U_i$ for $1 \leq i \leq N$.
Input
$N$ $U_1$ $U_2$ $\vdots$ $U_N$
Line $1$ contains the number of strings $N$.
The following $N$ lines contain the input strings. Line $i+1$ contains $U_i$.
$1 \leq N \leq 10^5$
$U_i$ is a string of length $3$ consisting only of lowercase letters a to z and uppercase letters A to Z.
Output
This problem uses a special judge.
If no strings $S_1, S_2, \dots, S_N, T_1, T_2, \dots, T_N$ satisfying the conditions exist, print Impossible.
Otherwise, on lines $1$ through $N$, print $S_i$ and $T_i$ separated by a space on the $i$-th line.
Any solution satisfying the conditions will be accepted.
Print a newline at the end.
Sample
Sample 1
Input
3 abc abd cbc
Output
a bc ab d cb c
$S_1=a, T_1=bc$
$S_2=ab, T_2=d$
$S_3=cb, T_3=c$
satisfies the conditions.
In this case, this is the only answer.
Sample 2
Input
2 aaa aaa
Output
Impossible
No $S_i,T_i$ satisfying the conditions exist, so print Impossible.
Note that $S_i$ and $T_i$ must be non-empty.
Sample 3
Input
2 aaa AAA
Output
a aa A AA
Uppercase and lowercase letters must be distinguished.
a aa
AA A
and other answers also exist.
Sample 4
Input
10 kgb cih blm kee lgj dcl bam ibc mca lkf
Output
k gb c ih b lm ke e l gj d cl ba m i bc mc a lk f
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。