AtCoder Regular Contest 003
B - さかさま辞書
Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB
問題文
逆さしりとりとは、前の人が言った単語の頭文字で終わる単語を答えるしりとりです。
しかし、高橋君は英単語に自信がないのでこっそり「さかさま辞書」を使うことにしました。
普通の辞書は単語の先頭の文字がABC順になるように並べられており、同じ文字同士の場合はその次の文字がABC順になるように並べられます。
先頭から見ていく普通の辞書順に対して、「さかさま辞書」は後ろの文字から見ていきます。
例えば apple, bee, card は、普通の辞書なら apple → bee → card の順になります。
しかし、「さかさま辞書」では d で終わる card が 1 番、apple とbee は同じ e で終わるのでその 1 つ前が e である bee が 2 番、l であるapple が 3 番の順になります。
図(a)：普通の辞書順に並べた例 図(b)：さかさま辞書順に並べた例
高橋君の代わりに「さかさま辞書」を作成し、与えられた単語を「さかさま辞書」順に並べてください。
入力
N
s_{1}
s_{2}
:
:
s_{N}
- 1 行目は、並べる単語数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
- 2 行目から N 行は、並べる単語を表す文字列が 1 行に 1 つずつ与えられる。
- i+1 行目の文字列 s_i の長さは 1 文字以上 20 文字以下で、含まれる文字はアルファベットの小文字のみ(
a-z)です。 - なお、重複する単語が与えられることはありません。
出力
なお、最後には改行を出力せよ。
入力例 1
5 chokudai kensho imos yuichirw ao
出力例 1
chokudai ao kensho imos yuichirw
- まず、それぞれの一番後ろの文字は、chokudai、kensho、imos、yuichirw、aoなのでABC順に並べると、i,o,s,wの順になります。
- しかしkenshoとaoの 2 人が同じ o なので、この 2 人に関してはその 1 つ前の文字の順で並べます。
- kenshoの後ろから 2 つ目の文字は h、ao の後ろから 2 つ目の文字は a なので、ao, kensho の順になります。
- よって、chokudai, ao, kensho, imos, yuichirw の順が答えになります。
入力例 2
2 dart art
出力例 2
art dart
- 後ろから 1,2,3 番目とも同じ文字なので、後ろから 4 番目の文字を比較します。
- しかし、art の後ろから 4 番目の文字はありません。
- 無い場合は、a よりも早いので、art, dart の順になります。