No.517 Broken Accessory
タグ : / 解いたユーザー数 161
作問者 :
nmnmnmnmnmnmnm
/ テスター :
ixmel
Problem Statement
Note: Reading Samples 1, 2, and 3 is quicker than reading the story.
Yuki and Kouda made accessories using strings.
An accessory consists of several stones, each with one letter of the alphabet drawn on it, connected in a single line by a cord.
The letters are uppercase, and no single accessory has two of the same letter.
When the stones are connected by the cord, a string can be read from the beginning to the end.
Yuki and Kouda made two accessories with the same string and each took one home.
10 years later.
Yuki and Kouda brought their accessories together.
However, the cords of the two accessories were weak, and they had broken in several places.
(The test cases also include cases where an accessory is not broken at all.)
Yuki and Kouda have completely forgotten what string was originally drawn.
Fortunately, none of the stones have been lost; all of them remain.
Can Yuki and Kouda recall the original string, using each other's broken accessories as clues?
If they can recall it, answer with that string.
If it is impossible, answer -1.
Input
$N$
$A_0$
$A_1$
$\vdots$
$A_{N-1}$
$M$
$B_0$
$B_1$
$\vdots$
$B_{M-1}$
N is the number of fragments of Yuki's accessory. $1\le N \le 26$.
$A_i$ is the string that can be read from the i-th fragment of Yuki's accessory.
M is the number of fragments of Kouda's accessory. $1\le M \le 26$.
$B_i$ is the string that can be read from the i-th fragment of Kouda's accessory.
The left-to-right direction of each string corresponds to the direction from the beginning to the end of the accessory.
All characters in the strings are uppercase letters of the alphabet.
A single accessory does not contain two or more of the same letter.
Every letter contained in Yuki's accessory is always contained in Kouda's accessory as well.
Output
If the string originally drawn on the accessory can be uniquely determined, output it on one line.
If it cannot be determined, output -1 on one line.
Do not forget the newline at the end.
Sample
Sample 1
Input
2 YUKI CODER 3 YU KICO DER
Output
YUKICODER
Yuki has two connected fragments of stones, "Y-U-K-I" and "C-O-D-E-R".
Kouda has three connected fragments, "Y-U", "K-I-C-O", and "D-E-R".
First, Kouda's information tells us that "I" and "C" are connected in this order.
It also tells us that Yuki's "Y-U-K-I" and "C-O-D-E-R" were originally connected in this order.
Therefore, the string of the accessory, whose letters are all distinct, can be determined to be "Y-U-K-I-C-O-D-E-R".
Sample 2
Input
2 EA T 2 T EA
Output
-1
The string may be "EAT" or it may be "TEA".
Since there are two possibilities, we cannot tell what the original string was.
Sample 3
Input
1 X 1 X
Output
X
The accessory had only the single letter "X", so the answer is also "X".
Sample 4
Input
4 MA V PWXHQ ID 5 H A QVM I DPWX
Output
IDPWXHQVMA
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。