No.470 Inverse S+T Problem
タグ : / 解いたユーザー数 111
作問者 :
ぴろず
/ テスター :
kimiyuki
問題文
文字列$S,T$に対して、$S$と$T$を結合したものを$S+T$で表します。
$N$個の長さ$3$の文字列$U_1,U_2,\dots,U_N$が与えられます。
$1 \leq i \leq N$について$S_i + T_i = U_i$となるような、$2N$個の相異なる空でない文字列$S_1, S_2, \dots, S_N, T_1, T_2, \dots, T_N$を求めて下さい。
入力
$N$ $U_1$ $U_2$ $\vdots$ $U_N$
$1$行目に文字列の個数$N$が与えられます。
続く$N$行は入力の文字列です。$i+1$行目に$U_i$が与えられます。
$1 \leq N \leq 10^5$
$U_i$は長さ$3$の文字列であり、小文字のaからzまたは大文字のAからZまでの文字のみを含む。
出力
この問題はスペシャルジャッジです。
条件を満たす文字列$S_1, S_2, \dots, S_N, T_1, T_2, \dots, T_N$が存在しない時、Impossibleと出力して下さい。
そうでない時、$1$行目から$N$行目まで、$i$行目に$S_i$と$T_i$をスペース区切りで出力してください。
このとき条件を満たしていればいずれの解も正解とみなされます。
最後に改行してください。
サンプル
サンプル1
入力
3 abc abd cbc
出力
a bc ab d cb c
$S_1=a, T_1=bc$
$S_2=ab, T_2=d$
$S_3=cb, T_3=c$
とすれば、条件を満たすことができます。
このケースでは、これが唯一の答えです。
サンプル2
入力
2 aaa aaa
出力
Impossible
条件を満たす$S_i,T_i$が存在しないので、Impossibleを出力します。
$S_i$や$T_i$は空でない必要があることに注意して下さい。
サンプル3
入力
2 aaa AAA
出力
a aa A AA
大文字と小文字は区別してください。
a aa
AA A
などの他の答えも存在します。
サンプル4
入力
10 kgb cih blm kee lgj dcl bam ibc mca lkf
出力
k gb c ih b lm ke e l gj d cl ba m i bc mc a lk f
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。