F - Fractal and Palindrome
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
シマウマ氏は,迷路に迷い込みました.迷路の中には,迷路と迷路がありました.
問題文
迷路
上図の迷路を解き,入口から出口への道筋で通った道に書かれた文字を順に並べた文字列を出力せよ.さらに,この文字列から E
をすべて除いたものが回文となるようにせよ (この条件を満たさない場合は部分点が与えられる).
詳細を以下に示す.
- 黒丸で示された地点の間を,矢印で表された一方通行の道によって移動できる.
- 図において交差していても,黒丸以外で他の道に移ることはできない.
- 内側の 2 個の正方形の中には,再帰的に外側の正方形の中と同じ構造が同じ向きに入っている.
- 最も外側の入口の頂点から最も外側の出口の頂点へ (すなわち,図に直接示された入口から図に直接示された出口へ) 辿り着かなければならない.
- 道に書かれた文字は,矢印の傍に矢印と同じ色で示されており,
A
,B
,C
,D
,E
のいずれかである. - 1 個の黒丸から出ている道に書かれた文字はすべて異なることが (内側,その内側,……の黒丸についても) 証明できる.
- 出力する文字列の長さは 1 以上 10^5 以下でなければならない.
部分点
- 正しく迷路を解いた文字列を出力した場合は,10 点が与えられる.
- さらに,その文字列から
E
をすべて除いたものが回文となる場合は,上記とは別に 90 点が与えられる.
入力
入力は空である.
出力
入口から出口への道筋で通った道に書かれた文字を順に並べた文字列を出力せよ.
形式が正しいが不正解となる出力例を以下に示す.
ABACABADABACABAEABACABADABACABA