← 返回题目列表

AtCoder · joisc2011_shiritori

shiritori. 知鸟

中文机器翻译题面 查看原题

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

しりとり (Shiritori) - 原题 PDF 第 1 页
原题PDF第6页
しりとり (Shiritori) - 原题 PDF 第 2 页
原题PDF第7页
しりとり (Shiritori) - 原题 PDF 第 3 页
原题PDF第8页
可复制的 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