E - 必殺！無限覇王斬！

Contest Duration: 2015-08-02(Sun) 04:00 - 2015-08-02(Sun) 09:00 (local time) (300 minutes) Back to Home

E - 必殺！無限覇王斬！ Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

実装難易度★★☆☆☆
謎解き難易度★☆☆☆☆

問題文

聖剣を入手した勇者はかっこいい必殺技を考えることにした。
勇者はかっこいい必殺技にはかっこいい名前が必要だと考え、
宿屋で夜更かしをしながら考えていた。
良いアイデアが思い浮かばずうとうとしていると、
夢の中で以下の様なイメージが浮かんできた。

イメージ

勇者が必殺技につけるべき名前はなんだろうか？

入力

本問題のみ入力にマルチバイト文字が含まれる。
マルチバイト文字は BOM (Byte Order Mark) なしの UTF-8 でエンコードされている。
入力は以下の形式で標準入力から与えられる。

 $N$ 
 $S_1$ 
 $S_2$ 
...
 $S_N$ 
　　 $L_1$ 　　
　　 $A_1$ 　　
 $L_2A_2□A_3L_3$ 
　　 $A_4$ 　　
　　 $L_4$

$1$ 行目には単語の数 $N (4 ≦ N ≦ 40,000)$ が与えられる。
$2$ 行目からの $N$ 行のうち $i$ 行目には $i$ 番目の単語 $S_i$ が与えられる。

$S_i$ は Unicode の 0x0021 ～ 0x007E (空白を除いた printable な ASCII 文字) または 0x4E00 ～ 0x9FFF (漢字) の範囲の文字からなる。
$S_i$ の長さ $|S_i|$ は $|S_i| = 2$ を満たす。
$i ≠ j$ のとき $S_i ≠ S_j$ が保証される。

$N + 2$ 行目からの $5$ 行には勇者が夢の中で得たイメージの情報が与えられる。

イメージの情報は $5$ 行 $5$ 列からなる。
$1$ 、 $2$ 、 $4$ 、 $5$ 行目の $1$ 、 $2$ 、 $4$ 、 $5$ 文字目はそれぞれ全角スペース　 (0x3000) である。
$1$ 行目の $3$ 文字目、 $3$ 行目の $1$ 文字目および $5$ 文字目、 $5$ 行目の $3$ 文字目は $S_1 ... S_N$ に含まれる文字のいずれかである。
$2$ 行目の $3$ 文字目および $4$ 行目の $3$ 文字目はそれぞれ ↑ (0x2191) または ↓ (0x2193) である。
$3$ 行目の $2$ 文字目および $3$ 行目の $4$ 文字目はそれぞれ ← (0x2190) または → (0x2192) である。
$3$ 行目の $3$ 文字目は □ (0x25AA) である。

出力

イメージから連想される文字 $1$ 文字を $1$ 行に出力せよ。
マルチバイト文字は BOM (Byte Order Mark) なしの UTF-8 でエンコードして出力せよ。
出力の末尾に改行を入れること。
答えは唯一に定まることが保証されている。

入力例 1

8
結構
連覇
覇王
草堂
覇道
覇者
慈愛
梵字
　　連　　
　　↓　　
者←□→道
　　↓　　
　　王

出力例 1

覇

入力例 2

6
王権
王制
口偏
王侯
王族
浜焼
　　制　　
　　↑　　
侯←□→権
　　↓　　
　　族

出力例 2

王

入力例 3

4
辻斬
斬髪
斬首
斬新
　　辻　　
　　↓　　
髪←□→新
　　↓　　
　　首

出力例 3

斬

入力例 4

4
AZ
BZ
ZC
ZD
　　A　　
　　↓　　
B→□→D
　　↓　　
　　C

出力例 4

注意

UTF-8 では 1 文字は 1 ～ 4 バイトで符号化されている。
C/C++ には標準で UTF-8 を扱うためのライブラリが存在しないため注意すること。
本問題の入力には 1 バイトまたは 3 バイトでエンコーディングされた文字のみが含まれる。
詳しくは “UTF-8 C++” 等で検索されることをおすすめする。