以下是来自日本的官方新闻原版PDF,已经完整保存和染色。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 2 – Shiritori
しりとり(Shiritori)
JOI 国では,100 種類の文字が使われている.これらの文字は,コンピュータ上では直接表すことが難し
いので,代わりに以下の表記が用いられる.
00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
すなわち,数字2 つによる10 × 10 通りで表される.JOI 国の辞書では,この表によって定まる文字の順
番によって単語を並べている.表の上の行にある文字がより早く,同じ行の文字ではより左の文字が早い.
さて,JOI 国では今,しりとりが一大ブームである.しりとりとは,参加者が順番に,前の人が言った単
語の最後の文字から始まる単語を言っていくゲームである.一度言われた単語を使うことはできない.
ある日,あなたは友達と「5 しりとり」で遊んでいた.「5 しりとり」では,通常のしりとりのルールに
加え,用いる単語はすべて5 文字でなければならない.あなたは「5 しりとり」で言われたN 個の単語の
リストをコンピュータに記録していたのだが,誤って並べ替えてしまった.そこで,単語のリストから「5
しりとり」の様子を復元したい.
課題
単語のリストが与えられたとき,「5 しりとり」の様子を復元するプログラムを作成せよ.
制限
1 ≦N ≦500 000 単語の個数
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれており,単語の個数を表す.
• 続くN 行には各単語が1 行に1 つずつ書かれている.各単語は数字ちょうど10 個からなる文字列で
表される.単語は辞書に掲載されている順に入力に書かれており,すべての単語は異なる.
しりとり– 1 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 2 – Shiritori
出力
与えられたN 個の単語を用いた「5 しりとり」が不可能である場合,impossible と1 行に出力せよ.
「5 しりとり」が可能である場合,用いられるN 個の単語を1 行1 つずつ出力せよ.可能な「5 しりと
り」が複数考えられるときは,以下の条件を満たすものを選べ.
• 1 番目の単語が辞書に最も早く掲載されているもの.
• 以上で定まらない場合は,2 番目の単語が辞書に最も早く掲載されているもの.
...
• 以上で定まらない場合は,N 番目の単語が辞書に最も早く掲載されているもの.
採点基準
採点用データのうち,配点の65%分については,現れる文字は00 から19 までの20 種類に限られる.
採点用データのうち,配点の65%分については,N ≦1 000 を満たす.
採点用データのうち,配点の40%分については,これら2 つの条件の両方を満たす.
採点用データのうち,配点の90%分については,これら2 つの条件の少なくとも一方を満たす.
入出力の例
入力例1 出力例1
5 0000010201
0000010201 0102030403
0102030403 0308090002
0104050603 0206070801
0206070801 0104050603
0308090002
この例では,以下の2 通りの「5 しりとり」が考えられる.
• 0000010201 →0102030403 →0308090002 →0206070801 →0104050603
• 0000010201 →0104050603 →0308090002 →0206070801 →0102030403
1 番目の単語は同じであり,2 番目の単語が辞書に掲載されている順番を比較して,前者を出力する.
しりとり– 2 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 2 – Shiritori
入力例2 出力例2
4 impossible
9600000098
9700000099
9800000099
9900000098
この例では,可能な「5 しりとり」は存在しない.
入力例3 出力例3
12 1909121313
0114090401 1313071203
0214051905 0304141219
0304141219 1902090011
0510031717 1108040907
0703050011 0703050011
1102190101 1110090702
1108040907 0214051905
1110090702 0510031717
1313071203 1707120711
1707120711 1102190101
1902090011 0114090401
1909121313
しりとり– 3 / 3