YUHA presents C88 謎解き×競技プログラミング 『ある勇者の物語』

E - 必殺!無限覇王斬!


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

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

問題文

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

イメージ

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

入力

本問題のみ入力にマルチバイト文字が含まれる。
マルチバイト文字は 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 行には勇者が夢の中で得たイメージの情報が与えられる。
    • イメージの情報は 55 列からなる。
    • 1245 行目の 1245 文字目はそれぞれ全角スペース   (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

Z

注意

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

Submit提出する