問題一覧 > 通常問題

No.205 マージして辞書順最小

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 175
作問者 : EmKjpEmKjp
6 ProblemId : 412 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:25

問題文

N 個の文字列 $S_1, ..., S_N$ が与えられる。 これらの文字列を以下のような手順でマージして、1つの文字列にする。

  1. 文字列 $T$ を空文字列に初期化する。
  2. $S_1, ..., S_N$ から空文字列ではない文字列 $S_k$をどれかひとつ選ぶ、そのような文字列がない場合は 文字列 $T$ を結果として返して終了する。
  3. $S_k$ の最初の一文字を文字列 $T$の一番最後に追加する。
  4. $S_k$ から最初の一文字を削除する。
  5. 2. に戻る。
上記のマージで生成されうる文字列の中で、辞書順最小のものを答えよ。

入力

$N$
$S_1$
$S_2$
...
$S_N$

$1 \le N \le 50$
$1 \le |S_i| \le 50$ ($1 \le i \le N$)
文字列 $S_i$ は、アルファベット小文字('a'~'z')で構成される。

出力

マージで生成されうる文字列のうち辞書順最小のものを出力してください。最後に改行してください。

サンプル

サンプル1
入力
1
abc
出力
abc

1つしか文字列がないので、マージして得られるのは "abc" の1通りのみです。

サンプル2
入力
2
ac
bd
出力
abcd

生成されうる文字列は、"abcd", "abdc", "acbd", "bacd", "badc", "bdac" の6つで、その中で辞書順最小になるのは "abcd" になります。

サンプル3
入力
5
one
two
three
four
five
出力
ffioneothreeturvewo

サンプル4
入力
2
az
za
出力
azaz

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。