/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
ストーリー
AtCoder社はオフィスの警備を行うロボットを開発中である。 ロボットは前方に壁があるかどうかに応じて状態と行動を変化させる 有限オートマトン によって制御される。 オートマトンの状態数、導入するロボットの台数、新たに設置する壁の枚数に応じて必要なコストは変化する。 オフィス全体が定期的に警備されるような、できるだけコストの低い方法を求めてほしい。
問題文
N\times N マスの盤面がある。 一番左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。 N\times N マスの外周は壁で囲まれており、隣接するマス間にも壁が存在する場合がある。
最大で N^2 台のロボットを導入できる。 各ロボットにはそれぞれ最大で 4N^2 通りの内部状態を設定できる。 ロボットは、前方が壁かどうか（すなわち、現在のマスから現在の向きに1マス進んだ先との間に壁があるかどうか）と現在の内部状態に応じて、直進・右折・左折の行動と次の内部状態を決定するオートマトンによって制御される。
直進(F)は現在の向きに1マス移動し、向きは変化しない。
右折(R)および左折(L)は他のマスへの移動を伴わない、その場での方向転換を指す。
1ステップの動作は次の順に行われる。 まず現在の（位置、向き、内部状態）から前方の壁の有無を判定する。 次に行動と次状態を決定する。 その後行動を実行し、最後に内部状態を次状態に更新する。
k 番目のロボットを制御するオートマトンの内部状態数を m_k とする。m_k は設計者が任意に定めてよい。 このとき、各状態 s=0,1,\cdots,m_k-1 について、以下を指定する。
- a_{k,s,0}: 前方が壁でない場合に、右折(
R)、左折(L)、直進(F)のいずれを行うか。 - b_{k,s,0}: 前方が壁でない場合の次の状態番号。
- a_{k,s,1}: 前方が壁の場合に、右折(
R)、左折(L)のいずれを行うか。直進(F)は選べない。 - b_{k,s,1}: 前方が壁の場合の次の状態番号。
例
内部状態数が2の、以下のようなオートマトンを考える。
s a_{k,s,0} b_{k,s,0} a_{k,s,1} b_{k,s,1} 0 F 0 R 1 1 R 0 R 0
このオートマトンは以下のように動作する。
- 内部状態が0のとき、前方に壁がない限り直進し、前方に壁があると右折して内部状態1に遷移する。
- 内部状態が1のとき、前方に壁があるかどうかに関わらず右折し、内部状態0に遷移する。
すなわち、前方に壁がない限り直進し、壁の直前でUターンする動作を繰り返す。
次に、各ロボット k に対し、初期配置における位置 (i_k,j_k) と向き d_k（上: U、下: D、左: L、右: R）を決定する。
内部状態の初期値は 0 である。
ロボット同士は互いに干渉せず、同じマスに複数台存在できる。
最後に、新たな壁を設置する。 壁は任意の隣接2マス間に設置できる。 すでに壁のある位置を指定してもよいが、単にコストが増えるだけで何も起こらない。 新たに導入する壁によって盤面が非連結となっても構わない。
各ロボットの（位置、向き、内部状態）の組は有限であり、同じ組に対する次時刻の（位置、向き、内部状態）の組は一意に定まる。 したがって、一定時間経過後は必ず周期的な行動に入る。 この周期的な行動中にロボットが訪れるマスを、そのロボットの警備対象マスと定義する。 周期的な行動に入る前にのみ訪れるマスは警備対象マスに含めない。
導入するロボットの台数を K、全ロボットの内部状態数の総和を M=\sum_k m_k、
出力において新たに設置すると指定した壁の本数（出力の 1 の個数）を W とする。
入力で与えられる係数 A_K、A_M、A_W に対し、導入コスト V を以下のように定義する。
\[ V = A_K \times (K-1) + A_M \times M + A_W \times W \]
全てのマスがいずれかのロボットの警備対象マスとなるような、できるだけ導入コストの低い方法を求めよ。 警備対象マスとならないマスが存在する場合、WA と判定される。
得点
導入コストが V のとき、以下の得点が得られる。
\[ 1+\mathrm{round}\left(10^6\times \max\left(0,\log_2 \frac{A_K (N^2-1) + A_M N^2}{V}\right)\right) \]
係数 A_K、A_M、A_W の違いにより、問題は A・B・C の 3 問 に分かれている。 それぞれの問題には 150 個のテストケース があり、各テストケースの得点の合計がその問題に対する提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 各問題に対して獲得した最高得点の総和で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数のチームが得た場合、提出時刻に関わらず同じ順位となる。
入力
入力は以下の形式で標準入力から与えられる。
N A_K A_M A_W
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
- 盤面サイズ N は全てのテストケースにおいて N=20 に固定されている。
- 導入コストの係数 A_K, A_M, A_W はそれぞれ 0 以上 1000 以下の整数である。
- v_{i,0} \cdots v_{i,N-2} は長さ N-1 の
0と1からなる文字列であり、j 文字目の文字 v_{i,j} は、マス (i, j) とマス (i, j+1) の間に壁がある（1）かない（0）かを表す。 - h_{i,0} \cdots h_{i,N-1} は長さ N の
0と1からなる文字列であり、j 文字目の文字 h_{i,j} は、マス (i, j) とマス (i+1, j) の間に壁がある（1）かない（0）かを表す。 - 初期状態において、全てのマスは互いに到達可能であることが保証されている。
出力
以下の形式で標準出力に出力せよ。
K
m_0 i_0 j_0 d_0
a_{0,0,0} b_{0,0,0} a_{0,0,1} b_{0,0,1}
\vdots
a_{0,m_0-1,0} b_{0,m_0-1,0} a_{0,m_0-1,1} b_{0,m_0-1,1}
\vdots
m_{K-1} i_{K-1} j_{K-1} d_{K-1}
a_{K-1,0,0} b_{K-1,0,0} a_{K-1,0,1} b_{K-1,0,1}
\vdots
a_{K-1,m_{K-1}-1,0} b_{K-1,m_{K-1}-1,0} a_{K-1,m_{K-1}-1,1} b_{K-1,m_{K-1}-1,1}
v_{0,0}' \cdots v_{0,N-2}'
\vdots
v_{N-1,0}' \cdots v_{N-1,N-2}'
h_{0,0}' \cdots h_{0,N-1}'
\vdots
h_{N-2,0}' \cdots h_{N-2,N-1}'
- K は開発するロボットの台数であり、1\leq K\leq N^2 を満たさなければならない。
- m_k は k 番目のロボットの内部状態数であり、1\leq m_k\leq 4N^2 を満たさなければならない。
- (i_k,j_k) は k 番目のロボットの初期位置であり、0\leq i_k,j_k\leq N-1 を満たさなければならない。
- d_k は k 番目のロボットの初期方向であり、上:
U、下:D、左:L、右:Rのいずれかの文字である。 - 各ロボット k について、内部状態 s=0,1,\dots,m_k-1 の順にちょうど m_k 行を出力しなければならない。
- a_{k,s,0}, a_{k,s,1} は、ロボット k が内部状態 s のときの行動を表す。前方が壁でない場合と壁である場合それぞれについて、右折:
R、左折:L、直進:Fのいずれかを指定する。ただし、a_{k,s,1} はFであってはならない。 - b_{k,s,0}, b_{k,s,1} は、ロボット k が内部状態 s のときの遷移先の内部状態番号を表す。前方が壁でない場合と壁である場合それぞれについて、0\leq b_{k,s,0}, b_{k,s,1}\leq m_k-1 を満たさなければならない。
- a_{k,s,0}, a_{k,s,1} は、ロボット k が内部状態 s のときの行動を表す。前方が壁でない場合と壁である場合それぞれについて、右折:
- v_{i,0}' \cdots v_{i,N-2}' は長さ N-1 の
0と1からなる文字列であり、j 文字目の文字 v_{i,j}' は、マス (i, j) とマス (i, j+1) の間に新たに壁を設置する（1）かしない（0）かを表す。 - h_{i,0}' \cdots h_{i,N-1}' は長さ N の
0と1からなる文字列であり、j 文字目の文字 h_{i,j}' は、マス (i, j) とマス (i+1, j) の間に新たに壁を設置する（1）かしない（0）かを表す。 - 壁の設置によって盤面が非連結になっても構わない。
サンプルプログラム
import sys
input = sys.stdin.readline
N, AK, AM, AW = map(int, input().split())
wall_v = [input().strip() for _ in range(N)]
wall_h = [input().strip() for _ in range(N - 1)]
K = N * N
print(K)
for i in range(N):
for j in range(N):
m = 1
d = 'U'
print(m, i, j, d)
print('R 0 R 0')
for _ in range(N):
print('0' * (N - 1))
for _ in range(N - 1):
print('0' * N)
入力生成方法
コスト係数の生成
各問題 A,B,C ごとに、以下の表に記載の範囲(閉区間)から一様ランダムに生成される。
| 問題 | A_K | A_M | A_W |
|---|---|---|---|
| A | [0,0] | [1,1] | [1000,1000] |
| B | [1000,1000] | [1,10] | [1,10] |
| C | [1000,1000] | [1,1] | [1000,1000] |
壁の生成
\mathrm{rand}(L, U) を、L 以上 U 以下の整数を一様ランダムに生成する関数とする。
まず、縦方向の壁生成回数 X=\mathrm{rand}(1,6) と横方向の壁生成回数 Y=\mathrm{rand}(1,6) を生成する。
壁が一枚も無い状態から開始して、以下のように壁を生成する。
以下の操作を X 回繰り返す。
- 壁を生成する方向を上または下からランダムに決定する。
- 壁の長さを L = \mathrm{rand}(5, 15) により生成する。
- 始点 (i, j) を i = \mathrm{rand}(0, N-1),\ j = \mathrm{rand}(0, N-2) により選択する。
- 上方向の場合は v_{i-L+1, j}, \cdots, v_{i, j} を、下方向の場合は v_{i, j}, \cdots, v_{i+L-1, j} を
1に設定する。ただし、添字が盤面の範囲外となる項は無視する。
以下の操作を Y 回繰り返す。
- 壁を生成する方向を左または右からランダムに決定する。
- 壁の長さを L = \mathrm{rand}(5, 15) により生成する。
- 始点 (i, j) を i = \mathrm{rand}(0, N-2),\ j = \mathrm{rand}(0, N-1) により選択する。
- 左方向の場合は h_{i, j-L+1}, \cdots, h_{i, j} を、右方向の場合は h_{i, j}, \cdots, h_{i, j+L-1} を
1に設定する。ただし、添字が盤面の範囲外となる項は無視する。
生成した壁に対し、すべてのマスが到達可能であるかを判定する。到達不能な場合は壁を初期化して X+Y 回の壁生成をやり直す（X,Y は再生成しない）。
ツール(入力ジェネレータ・スコア計算)
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、チーム外とのビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。
入力例 1
20 0 1 1000 0010000000000000000 0010000000000000000 0010000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000010000 0001000000000010000 0001010000000010000 0001010000000010000 0001010000000010000 0001010000000010000 0000010000000010000 0000000000000010000 0000000000000000000 00000000000000000000 00000000111111111110 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000
出力例 1
400 1 0 0 U R 0 R 0 1 0 1 U R 0 R 0 1 0 2 U R 0 R 0 1 0 3 U R 0 R 0 1 0 4 U R 0 R 0 1 0 5 U R 0 R 0 1 0 6 U R 0 R 0 1 0 7 U R 0 R 0 1 0 8 U R 0 R 0 1 0 9 U R 0 R 0 1 0 10 U R 0 R 0 1 0 11 U R 0 R 0 1 0 12 U R 0 R 0 1 0 13 U R 0 R 0 1 0 14 U R 0 R 0 1 0 15 U R 0 R 0 1 0 16 U R 0 R 0 1 0 17 U R 0 R 0 1 0 18 U R 0 R 0 1 0 19 U R 0 R 0 1 1 0 U R 0 R 0 1 1 1 U R 0 R 0 1 1 2 U R 0 R 0 1 1 3 U R 0 R 0 1 1 4 U R 0 R 0 1 1 5 U R 0 R 0 1 1 6 U R 0 R 0 1 1 7 U R 0 R 0 1 1 8 U R 0 R 0 1 1 9 U R 0 R 0 1 1 10 U R 0 R 0 1 1 11 U R 0 R 0 1 1 12 U R 0 R 0 1 1 13 U R 0 R 0 1 1 14 U R 0 R 0 1 1 15 U R 0 R 0 1 1 16 U R 0 R 0 1 1 17 U R 0 R 0 1 1 18 U R 0 R 0 1 1 19 U R 0 R 0 1 2 0 U R 0 R 0 1 2 1 U R 0 R 0 1 2 2 U R 0 R 0 1 2 3 U R 0 R 0 1 2 4 U R 0 R 0 1 2 5 U R 0 R 0 1 2 6 U R 0 R 0 1 2 7 U R 0 R 0 1 2 8 U R 0 R 0 1 2 9 U R 0 R 0 1 2 10 U R 0 R 0 1 2 11 U R 0 R 0 1 2 12 U R 0 R 0 1 2 13 U R 0 R 0 1 2 14 U R 0 R 0 1 2 15 U R 0 R 0 1 2 16 U R 0 R 0 1 2 17 U R 0 R 0 1 2 18 U R 0 R 0 1 2 19 U R 0 R 0 1 3 0 U R 0 R 0 1 3 1 U R 0 R 0 1 3 2 U R 0 R 0 1 3 3 U R 0 R 0 1 3 4 U R 0 R 0 1 3 5 U R 0 R 0 1 3 6 U R 0 R 0 1 3 7 U R 0 R 0 1 3 8 U R 0 R 0 1 3 9 U R 0 R 0 1 3 10 U R 0 R 0 1 3 11 U R 0 R 0 1 3 12 U R 0 R 0 1 3 13 U R 0 R 0 1 3 14 U R 0 R 0 1 3 15 U R 0 R 0 1 3 16 U R 0 R 0 1 3 17 U R 0 R 0 1 3 18 U R 0 R 0 1 3 19 U R 0 R 0 1 4 0 U R 0 R 0 1 4 1 U R 0 R 0 1 4 2 U R 0 R 0 1 4 3 U R 0 R 0 1 4 4 U R 0 R 0 1 4 5 U R 0 R 0 1 4 6 U R 0 R 0 1 4 7 U R 0 R 0 1 4 8 U R 0 R 0 1 4 9 U R 0 R 0 1 4 10 U R 0 R 0 1 4 11 U R 0 R 0 1 4 12 U R 0 R 0 1 4 13 U R 0 R 0 1 4 14 U R 0 R 0 1 4 15 U R 0 R 0 1 4 16 U R 0 R 0 1 4 17 U R 0 R 0 1 4 18 U R 0 R 0 1 4 19 U R 0 R 0 1 5 0 U R 0 R 0 1 5 1 U R 0 R 0 1 5 2 U R 0 R 0 1 5 3 U R 0 R 0 1 5 4 U R 0 R 0 1 5 5 U R 0 R 0 1 5 6 U R 0 R 0 1 5 7 U R 0 R 0 1 5 8 U R 0 R 0 1 5 9 U R 0 R 0 1 5 10 U R 0 R 0 1 5 11 U R 0 R 0 1 5 12 U R 0 R 0 1 5 13 U R 0 R 0 1 5 14 U R 0 R 0 1 5 15 U R 0 R 0 1 5 16 U R 0 R 0 1 5 17 U R 0 R 0 1 5 18 U R 0 R 0 1 5 19 U R 0 R 0 1 6 0 U R 0 R 0 1 6 1 U R 0 R 0 1 6 2 U R 0 R 0 1 6 3 U R 0 R 0 1 6 4 U R 0 R 0 1 6 5 U R 0 R 0 1 6 6 U R 0 R 0 1 6 7 U R 0 R 0 1 6 8 U R 0 R 0 1 6 9 U R 0 R 0 1 6 10 U R 0 R 0 1 6 11 U R 0 R 0 1 6 12 U R 0 R 0 1 6 13 U R 0 R 0 1 6 14 U R 0 R 0 1 6 15 U R 0 R 0 1 6 16 U R 0 R 0 1 6 17 U R 0 R 0 1 6 18 U R 0 R 0 1 6 19 U R 0 R 0 1 7 0 U R 0 R 0 1 7 1 U R 0 R 0 1 7 2 U R 0 R 0 1 7 3 U R 0 R 0 1 7 4 U R 0 R 0 1 7 5 U R 0 R 0 1 7 6 U R 0 R 0 1 7 7 U R 0 R 0 1 7 8 U R 0 R 0 1 7 9 U R 0 R 0 1 7 10 U R 0 R 0 1 7 11 U R 0 R 0 1 7 12 U R 0 R 0 1 7 13 U R 0 R 0 1 7 14 U R 0 R 0 1 7 15 U R 0 R 0 1 7 16 U R 0 R 0 1 7 17 U R 0 R 0 1 7 18 U R 0 R 0 1 7 19 U R 0 R 0 1 8 0 U R 0 R 0 1 8 1 U R 0 R 0 1 8 2 U R 0 R 0 1 8 3 U R 0 R 0 1 8 4 U R 0 R 0 1 8 5 U R 0 R 0 1 8 6 U R 0 R 0 1 8 7 U R 0 R 0 1 8 8 U R 0 R 0 1 8 9 U R 0 R 0 1 8 10 U R 0 R 0 1 8 11 U R 0 R 0 1 8 12 U R 0 R 0 1 8 13 U R 0 R 0 1 8 14 U R 0 R 0 1 8 15 U R 0 R 0 1 8 16 U R 0 R 0 1 8 17 U R 0 R 0 1 8 18 U R 0 R 0 1 8 19 U R 0 R 0 1 9 0 U R 0 R 0 1 9 1 U R 0 R 0 1 9 2 U R 0 R 0 1 9 3 U R 0 R 0 1 9 4 U R 0 R 0 1 9 5 U R 0 R 0 1 9 6 U R 0 R 0 1 9 7 U R 0 R 0 1 9 8 U R 0 R 0 1 9 9 U R 0 R 0 1 9 10 U R 0 R 0 1 9 11 U R 0 R 0 1 9 12 U R 0 R 0 1 9 13 U R 0 R 0 1 9 14 U R 0 R 0 1 9 15 U R 0 R 0 1 9 16 U R 0 R 0 1 9 17 U R 0 R 0 1 9 18 U R 0 R 0 1 9 19 U R 0 R 0 1 10 0 U R 0 R 0 1 10 1 U R 0 R 0 1 10 2 U R 0 R 0 1 10 3 U R 0 R 0 1 10 4 U R 0 R 0 1 10 5 U R 0 R 0 1 10 6 U R 0 R 0 1 10 7 U R 0 R 0 1 10 8 U R 0 R 0 1 10 9 U R 0 R 0 1 10 10 U R 0 R 0 1 10 11 U R 0 R 0 1 10 12 U R 0 R 0 1 10 13 U R 0 R 0 1 10 14 U R 0 R 0 1 10 15 U R 0 R 0 1 10 16 U R 0 R 0 1 10 17 U R 0 R 0 1 10 18 U R 0 R 0 1 10 19 U R 0 R 0 1 11 0 U R 0 R 0 1 11 1 U R 0 R 0 1 11 2 U R 0 R 0 1 11 3 U R 0 R 0 1 11 4 U R 0 R 0 1 11 5 U R 0 R 0 1 11 6 U R 0 R 0 1 11 7 U R 0 R 0 1 11 8 U R 0 R 0 1 11 9 U R 0 R 0 1 11 10 U R 0 R 0 1 11 11 U R 0 R 0 1 11 12 U R 0 R 0 1 11 13 U R 0 R 0 1 11 14 U R 0 R 0 1 11 15 U R 0 R 0 1 11 16 U R 0 R 0 1 11 17 U R 0 R 0 1 11 18 U R 0 R 0 1 11 19 U R 0 R 0 1 12 0 U R 0 R 0 1 12 1 U R 0 R 0 1 12 2 U R 0 R 0 1 12 3 U R 0 R 0 1 12 4 U R 0 R 0 1 12 5 U R 0 R 0 1 12 6 U R 0 R 0 1 12 7 U R 0 R 0 1 12 8 U R 0 R 0 1 12 9 U R 0 R 0 1 12 10 U R 0 R 0 1 12 11 U R 0 R 0 1 12 12 U R 0 R 0 1 12 13 U R 0 R 0 1 12 14 U R 0 R 0 1 12 15 U R 0 R 0 1 12 16 U R 0 R 0 1 12 17 U R 0 R 0 1 12 18 U R 0 R 0 1 12 19 U R 0 R 0 1 13 0 U R 0 R 0 1 13 1 U R 0 R 0 1 13 2 U R 0 R 0 1 13 3 U R 0 R 0 1 13 4 U R 0 R 0 1 13 5 U R 0 R 0 1 13 6 U R 0 R 0 1 13 7 U R 0 R 0 1 13 8 U R 0 R 0 1 13 9 U R 0 R 0 1 13 10 U R 0 R 0 1 13 11 U R 0 R 0 1 13 12 U R 0 R 0 1 13 13 U R 0 R 0 1 13 14 U R 0 R 0 1 13 15 U R 0 R 0 1 13 16 U R 0 R 0 1 13 17 U R 0 R 0 1 13 18 U R 0 R 0 1 13 19 U R 0 R 0 1 14 0 U R 0 R 0 1 14 1 U R 0 R 0 1 14 2 U R 0 R 0 1 14 3 U R 0 R 0 1 14 4 U R 0 R 0 1 14 5 U R 0 R 0 1 14 6 U R 0 R 0 1 14 7 U R 0 R 0 1 14 8 U R 0 R 0 1 14 9 U R 0 R 0 1 14 10 U R 0 R 0 1 14 11 U R 0 R 0 1 14 12 U R 0 R 0 1 14 13 U R 0 R 0 1 14 14 U R 0 R 0 1 14 15 U R 0 R 0 1 14 16 U R 0 R 0 1 14 17 U R 0 R 0 1 14 18 U R 0 R 0 1 14 19 U R 0 R 0 1 15 0 U R 0 R 0 1 15 1 U R 0 R 0 1 15 2 U R 0 R 0 1 15 3 U R 0 R 0 1 15 4 U R 0 R 0 1 15 5 U R 0 R 0 1 15 6 U R 0 R 0 1 15 7 U R 0 R 0 1 15 8 U R 0 R 0 1 15 9 U R 0 R 0 1 15 10 U R 0 R 0 1 15 11 U R 0 R 0 1 15 12 U R 0 R 0 1 15 13 U R 0 R 0 1 15 14 U R 0 R 0 1 15 15 U R 0 R 0 1 15 16 U R 0 R 0 1 15 17 U R 0 R 0 1 15 18 U R 0 R 0 1 15 19 U R 0 R 0 1 16 0 U R 0 R 0 1 16 1 U R 0 R 0 1 16 2 U R 0 R 0 1 16 3 U R 0 R 0 1 16 4 U R 0 R 0 1 16 5 U R 0 R 0 1 16 6 U R 0 R 0 1 16 7 U R 0 R 0 1 16 8 U R 0 R 0 1 16 9 U R 0 R 0 1 16 10 U R 0 R 0 1 16 11 U R 0 R 0 1 16 12 U R 0 R 0 1 16 13 U R 0 R 0 1 16 14 U R 0 R 0 1 16 15 U R 0 R 0 1 16 16 U R 0 R 0 1 16 17 U R 0 R 0 1 16 18 U R 0 R 0 1 16 19 U R 0 R 0 1 17 0 U R 0 R 0 1 17 1 U R 0 R 0 1 17 2 U R 0 R 0 1 17 3 U R 0 R 0 1 17 4 U R 0 R 0 1 17 5 U R 0 R 0 1 17 6 U R 0 R 0 1 17 7 U R 0 R 0 1 17 8 U R 0 R 0 1 17 9 U R 0 R 0 1 17 10 U R 0 R 0 1 17 11 U R 0 R 0 1 17 12 U R 0 R 0 1 17 13 U R 0 R 0 1 17 14 U R 0 R 0 1 17 15 U R 0 R 0 1 17 16 U R 0 R 0 1 17 17 U R 0 R 0 1 17 18 U R 0 R 0 1 17 19 U R 0 R 0 1 18 0 U R 0 R 0 1 18 1 U R 0 R 0 1 18 2 U R 0 R 0 1 18 3 U R 0 R 0 1 18 4 U R 0 R 0 1 18 5 U R 0 R 0 1 18 6 U R 0 R 0 1 18 7 U R 0 R 0 1 18 8 U R 0 R 0 1 18 9 U R 0 R 0 1 18 10 U R 0 R 0 1 18 11 U R 0 R 0 1 18 12 U R 0 R 0 1 18 13 U R 0 R 0 1 18 14 U R 0 R 0 1 18 15 U R 0 R 0 1 18 16 U R 0 R 0 1 18 17 U R 0 R 0 1 18 18 U R 0 R 0 1 18 19 U R 0 R 0 1 19 0 U R 0 R 0 1 19 1 U R 0 R 0 1 19 2 U R 0 R 0 1 19 3 U R 0 R 0 1 19 4 U R 0 R 0 1 19 5 U R 0 R 0 1 19 6 U R 0 R 0 1 19 7 U R 0 R 0 1 19 8 U R 0 R 0 1 19 9 U R 0 R 0 1 19 10 U R 0 R 0 1 19 11 U R 0 R 0 1 19 12 U R 0 R 0 1 19 13 U R 0 R 0 1 19 14 U R 0 R 0 1 19 15 U R 0 R 0 1 19 16 U R 0 R 0 1 19 17 U R 0 R 0 1 19 18 U R 0 R 0 1 19 19 U R 0 R 0 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000
Story
AtCoder Inc. is developing robots to guard its office. Each robot is controlled by a finite-state automaton that changes its state and actions depending on whether there is a wall in front of it. The required cost varies depending on the number of states in the automaton, the number of robots to be introduced, and the number of new walls to be installed. Please find a method with as low a cost as possible such that the entire office is patrolled periodically.
Problem Statement
There is an N\times N grid. Let the coordinates of the top-left cell be (0,0), and define the coordinates of the cell reached by moving i cells downward and j cells to the right from there as (i,j). The outer boundary of the N\times N grid is surrounded by walls, and there may also be walls between adjacent cells.
Up to N^2 robots can be introduced. For each robot, up to 4N^2 internal states can be defined. Each robot is controlled by an automaton that, depending on whether there is a wall in front of it (i.e., whether there is a wall between the current cell and the cell one step ahead in the current direction) and its current internal state, determines an action among going forward, turning right, and turning left, as well as the next internal state.
Going forward (F) moves one cell forward in the current direction, and the direction does not change.
Turning right (R) and turning left (L) refer to changing direction in place without moving to another cell.
One step of operation is performed in the following order. First, from the current (position, direction, internal state), the robot determines whether there is a wall in front. Next, it determines the action and the next state. Then it performs the action, and finally it updates the internal state to the next state.
Let m_k be the number of internal states of the automaton that controls the k-th robot. You may choose m_k arbitrarily. Then, for each state s=0,1,\cdots,m_k-1, specify the following.
- a_{k,s,0}: Which of turning right (
R), turning left (L), or going forward (F) to perform when there is no wall in front. - b_{k,s,0}: The next state number when there is no wall in front.
- a_{k,s,1}: Which of turning right (
R) or turning left (L) to perform when there is a wall in front. Going forward (F) cannot be chosen. - b_{k,s,1}: The next state number when there is a wall in front.
Example
Consider the following automaton with 2 internal states.
s a_{k,s,0} b_{k,s,0} a_{k,s,1} b_{k,s,1} 0 F 0 R 1 1 R 0 R 0
This automaton operates as follows.
- When the internal state is 0, it goes forward as long as there is no wall in front, and if there is a wall in front, it turns right and transitions to internal state 1.
- When the internal state is 1, it turns right regardless of whether there is a wall in front, and transitions to internal state 0.
In other words, it repeats the behavior of going forward as long as there is no wall in front, and making a U-turn just in front of a wall.
Next, for each robot k, determine its position (i_k,j_k) and direction d_k in the initial placement (up: U, down: D, left: L, right: R).
The initial value of the internal state is 0.
Robots do not interfere with each other, and multiple robots may occupy the same cell.
Finally, install new walls. A wall can be installed between any two adjacent cells. You may specify a position where a wall already exists, but nothing happens other than increasing the cost. It is allowed for the board to become disconnected due to newly installed walls.
For each robot, the set of (position, direction, internal state) is finite, and the next-time (position, direction, internal state) corresponding to the same set is uniquely determined. Therefore, after some time has passed, it will inevitably enter periodic behavior. Define the cells that the robot visits during this periodic behavior as the cells patrolled by that robot. Cells that are visited only before entering periodic behavior are not included in the cells patrolled.
Let K be the number of robots to be introduced, let M=\sum_k m_k be the total number of internal states over all robots,
and let W be the number of newly installed walls specified in the output (the number of 1s in the output).
Given the coefficients A_K, A_M, and A_W provided in the input, define the introduction cost V as follows.
\[ V = A_K \times (K-1) + A_M \times M + A_W \times W \]
Find a method with as low an introduction cost as possible such that every cell becomes a cell patrolled by at least one robot. If there exists a cell that does not become a patrolled cell, it will be judged as WA.
Scoring
When the introduction cost is V, you obtain the following score.
\[ 1+\mathrm{round}\left(10^6\times \max\left(0,\log_2 \frac{A_K (N^2-1) + A_M N^2}{V}\right)\right) \]
Depending on the coefficients A_K, A_M, and A_W, the problem is divided into three subproblems: A, B, and C. Each subproblem contains 150 test cases, and the total score for a submission to that subproblem is the sum of the scores from all test cases in it. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero.
The final ranking is determined by the sum of the highest scores obtained for each subproblem, and there will be no system test after the contest. If more than one team gets the same score, they will be ranked in the same place regardless of the submission time.
Input
The input is given from Standard Input in the following format.
N A_K A_M A_W
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
- The board size N is fixed to N=20 for all test cases.
- The coefficients A_K, A_M, and A_W of the introduction cost are integers between 0 and 1000, inclusive.
- v_{i,0} \cdots v_{i,N-2} is a string of length N-1 consisting of
0and1, and the j-th character v_{i,j} indicates whether there is (1) or is not (0) a wall between cell (i, j) and cell (i, j+1). - h_{i,0} \cdots h_{i,N-1} is a string of length N consisting of
0and1, and the j-th character h_{i,j} indicates whether there is (1) or is not (0) a wall between cell (i, j) and cell (i+1, j). - In the initial state, it is guaranteed that all cells are mutually reachable.
Output
Print to Standard Output in the following format.
K
m_0 i_0 j_0 d_0
a_{0,0,0} b_{0,0,0} a_{0,0,1} b_{0,0,1}
\vdots
a_{0,m_0-1,0} b_{0,m_0-1,0} a_{0,m_0-1,1} b_{0,m_0-1,1}
\vdots
m_{K-1} i_{K-1} j_{K-1} d_{K-1}
a_{K-1,0,0} b_{K-1,0,0} a_{K-1,0,1} b_{K-1,0,1}
\vdots
a_{K-1,m_{K-1}-1,0} b_{K-1,m_{K-1}-1,0} a_{K-1,m_{K-1}-1,1} b_{K-1,m_{K-1}-1,1}
v_{0,0}' \cdots v_{0,N-2}'
\vdots
v_{N-1,0}' \cdots v_{N-1,N-2}'
h_{0,0}' \cdots h_{0,N-1}'
\vdots
h_{N-2,0}' \cdots h_{N-2,N-1}'
- K is the number of robots to be developed, and it must satisfy 1\leq K\leq N^2.
- m_k is the number of internal states of the k-th robot, and it must satisfy 1\leq m_k\leq 4N^2.
- (i_k,j_k) is the initial position of the k-th robot, and it must satisfy 0\leq i_k,j_k\leq N-1.
- d_k is the initial direction of the k-th robot, and is one of the characters up:
U, down:D, left:L, right:R. - For each robot k, you must output exactly m_k lines in the order of internal state s=0,1,\dots,m_k-1.
- a_{k,s,0} and a_{k,s,1} represent the action of robot k when its internal state is s. For the cases where there is no wall in front and where there is a wall in front, respectively, specify one of turn right:
R, turn left:L, or go forward:F. However, a_{k,s,1} must not beF. - b_{k,s,0} and b_{k,s,1} represent the next internal state number when robot k is in internal state s. For the cases where there is no wall in front and where there is a wall in front, respectively, they must satisfy 0\leq b_{k,s,0}, b_{k,s,1}\leq m_k-1.
- a_{k,s,0} and a_{k,s,1} represent the action of robot k when its internal state is s. For the cases where there is no wall in front and where there is a wall in front, respectively, specify one of turn right:
- v_{i,0}' \cdots v_{i,N-2}' is a string of length N-1 consisting of
0and1, and the j-th character v_{i,j}' indicates whether to install (1) or not install (0) a new wall between cell (i, j) and cell (i, j+1). - h_{i,0}' \cdots h_{i,N-1}' is a string of length N consisting of
0and1, and the j-th character h_{i,j}' indicates whether to install (1) or not install (0) a new wall between cell (i, j) and cell (i+1, j). - The board may become disconnected due to wall installation.
Sample Solution
import sys
input = sys.stdin.readline
N, AK, AM, AW = map(int, input().split())
wall_v = [input().strip() for _ in range(N)]
wall_h = [input().strip() for _ in range(N - 1)]
K = N * N
print(K)
for i in range(N):
for j in range(N):
m = 1
d = 'U'
print(m, i, j, d)
print('R 0 R 0')
for _ in range(N):
print('0' * (N - 1))
for _ in range(N - 1):
print('0' * N)
Input Generation
For each of the tasks A, B, and C, the coefficients are generated uniformly at random from the ranges (closed intervals) listed in the following table.
| Task | A_K | A_M | A_W |
|---|---|---|---|
| A | [0,0] | [1,1] | [1000,1000] |
| B | [1000,1000] | [1,10] | [1,10] |
| C | [1000,1000] | [1,1] | [1000,1000] |
Generation of walls
Let \mathrm{rand}(L, U) be a function that generates an integer uniformly at random between L and U, inclusive.
First, generate the number of vertical wall generations X=\mathrm{rand}(1,6) and the number of horizontal wall generations Y=\mathrm{rand}(1,6).
Starting from a state with no walls at all, generate walls as follows.
Repeat the following operation X times.
- Randomly decide whether to generate the wall upward or downward.
- Generate the wall length by L = \mathrm{rand}(5, 15).
- Choose the starting point (i, j) by i = \mathrm{rand}(0, N-1),\ j = \mathrm{rand}(0, N-2).
- If the direction is upward, set v_{i-L+1, j}, \cdots, v_{i, j} to
1; if the direction is downward, set v_{i, j}, \cdots, v_{i+L-1, j} to1. Terms whose indices go out of the board range are ignored.
Repeat the following operation Y times.
- Randomly decide whether to generate the wall from the left or from the right.
- Generate the wall length by L = \mathrm{rand}(5, 15).
- Choose the starting point (i, j) by i = \mathrm{rand}(0, N-2),\ j = \mathrm{rand}(0, N-1).
- If the direction is leftward, set h_{i, j-L+1}, \cdots, h_{i, j} to
1; if the direction is rightward, set h_{i, j}, \cdots, h_{i, j+L-1} to1. Terms whose indices go out of the board range are ignored.
For the generated walls, check whether all cells are reachable. If some cells are unreachable, reset the walls and redo the wall generation (do not regenerate X and Y).
Tools (Input generator and score calculation)
- Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
Please be aware that sharing visualization results or discussing solutions/ideas outside of the team during the contest is prohibited.
Sample Input 1
20 0 1 1000 0010000000000000000 0010000000000000000 0010000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000000000 0001000000000010000 0001000000000010000 0001010000000010000 0001010000000010000 0001010000000010000 0001010000000010000 0000010000000010000 0000000000000010000 0000000000000000000 00000000000000000000 00000000111111111110 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000
Sample Output 1
400 1 0 0 U R 0 R 0 1 0 1 U R 0 R 0 1 0 2 U R 0 R 0 1 0 3 U R 0 R 0 1 0 4 U R 0 R 0 1 0 5 U R 0 R 0 1 0 6 U R 0 R 0 1 0 7 U R 0 R 0 1 0 8 U R 0 R 0 1 0 9 U R 0 R 0 1 0 10 U R 0 R 0 1 0 11 U R 0 R 0 1 0 12 U R 0 R 0 1 0 13 U R 0 R 0 1 0 14 U R 0 R 0 1 0 15 U R 0 R 0 1 0 16 U R 0 R 0 1 0 17 U R 0 R 0 1 0 18 U R 0 R 0 1 0 19 U R 0 R 0 1 1 0 U R 0 R 0 1 1 1 U R 0 R 0 1 1 2 U R 0 R 0 1 1 3 U R 0 R 0 1 1 4 U R 0 R 0 1 1 5 U R 0 R 0 1 1 6 U R 0 R 0 1 1 7 U R 0 R 0 1 1 8 U R 0 R 0 1 1 9 U R 0 R 0 1 1 10 U R 0 R 0 1 1 11 U R 0 R 0 1 1 12 U R 0 R 0 1 1 13 U R 0 R 0 1 1 14 U R 0 R 0 1 1 15 U R 0 R 0 1 1 16 U R 0 R 0 1 1 17 U R 0 R 0 1 1 18 U R 0 R 0 1 1 19 U R 0 R 0 1 2 0 U R 0 R 0 1 2 1 U R 0 R 0 1 2 2 U R 0 R 0 1 2 3 U R 0 R 0 1 2 4 U R 0 R 0 1 2 5 U R 0 R 0 1 2 6 U R 0 R 0 1 2 7 U R 0 R 0 1 2 8 U R 0 R 0 1 2 9 U R 0 R 0 1 2 10 U R 0 R 0 1 2 11 U R 0 R 0 1 2 12 U R 0 R 0 1 2 13 U R 0 R 0 1 2 14 U R 0 R 0 1 2 15 U R 0 R 0 1 2 16 U R 0 R 0 1 2 17 U R 0 R 0 1 2 18 U R 0 R 0 1 2 19 U R 0 R 0 1 3 0 U R 0 R 0 1 3 1 U R 0 R 0 1 3 2 U R 0 R 0 1 3 3 U R 0 R 0 1 3 4 U R 0 R 0 1 3 5 U R 0 R 0 1 3 6 U R 0 R 0 1 3 7 U R 0 R 0 1 3 8 U R 0 R 0 1 3 9 U R 0 R 0 1 3 10 U R 0 R 0 1 3 11 U R 0 R 0 1 3 12 U R 0 R 0 1 3 13 U R 0 R 0 1 3 14 U R 0 R 0 1 3 15 U R 0 R 0 1 3 16 U R 0 R 0 1 3 17 U R 0 R 0 1 3 18 U R 0 R 0 1 3 19 U R 0 R 0 1 4 0 U R 0 R 0 1 4 1 U R 0 R 0 1 4 2 U R 0 R 0 1 4 3 U R 0 R 0 1 4 4 U R 0 R 0 1 4 5 U R 0 R 0 1 4 6 U R 0 R 0 1 4 7 U R 0 R 0 1 4 8 U R 0 R 0 1 4 9 U R 0 R 0 1 4 10 U R 0 R 0 1 4 11 U R 0 R 0 1 4 12 U R 0 R 0 1 4 13 U R 0 R 0 1 4 14 U R 0 R 0 1 4 15 U R 0 R 0 1 4 16 U R 0 R 0 1 4 17 U R 0 R 0 1 4 18 U R 0 R 0 1 4 19 U R 0 R 0 1 5 0 U R 0 R 0 1 5 1 U R 0 R 0 1 5 2 U R 0 R 0 1 5 3 U R 0 R 0 1 5 4 U R 0 R 0 1 5 5 U R 0 R 0 1 5 6 U R 0 R 0 1 5 7 U R 0 R 0 1 5 8 U R 0 R 0 1 5 9 U R 0 R 0 1 5 10 U R 0 R 0 1 5 11 U R 0 R 0 1 5 12 U R 0 R 0 1 5 13 U R 0 R 0 1 5 14 U R 0 R 0 1 5 15 U R 0 R 0 1 5 16 U R 0 R 0 1 5 17 U R 0 R 0 1 5 18 U R 0 R 0 1 5 19 U R 0 R 0 1 6 0 U R 0 R 0 1 6 1 U R 0 R 0 1 6 2 U R 0 R 0 1 6 3 U R 0 R 0 1 6 4 U R 0 R 0 1 6 5 U R 0 R 0 1 6 6 U R 0 R 0 1 6 7 U R 0 R 0 1 6 8 U R 0 R 0 1 6 9 U R 0 R 0 1 6 10 U R 0 R 0 1 6 11 U R 0 R 0 1 6 12 U R 0 R 0 1 6 13 U R 0 R 0 1 6 14 U R 0 R 0 1 6 15 U R 0 R 0 1 6 16 U R 0 R 0 1 6 17 U R 0 R 0 1 6 18 U R 0 R 0 1 6 19 U R 0 R 0 1 7 0 U R 0 R 0 1 7 1 U R 0 R 0 1 7 2 U R 0 R 0 1 7 3 U R 0 R 0 1 7 4 U R 0 R 0 1 7 5 U R 0 R 0 1 7 6 U R 0 R 0 1 7 7 U R 0 R 0 1 7 8 U R 0 R 0 1 7 9 U R 0 R 0 1 7 10 U R 0 R 0 1 7 11 U R 0 R 0 1 7 12 U R 0 R 0 1 7 13 U R 0 R 0 1 7 14 U R 0 R 0 1 7 15 U R 0 R 0 1 7 16 U R 0 R 0 1 7 17 U R 0 R 0 1 7 18 U R 0 R 0 1 7 19 U R 0 R 0 1 8 0 U R 0 R 0 1 8 1 U R 0 R 0 1 8 2 U R 0 R 0 1 8 3 U R 0 R 0 1 8 4 U R 0 R 0 1 8 5 U R 0 R 0 1 8 6 U R 0 R 0 1 8 7 U R 0 R 0 1 8 8 U R 0 R 0 1 8 9 U R 0 R 0 1 8 10 U R 0 R 0 1 8 11 U R 0 R 0 1 8 12 U R 0 R 0 1 8 13 U R 0 R 0 1 8 14 U R 0 R 0 1 8 15 U R 0 R 0 1 8 16 U R 0 R 0 1 8 17 U R 0 R 0 1 8 18 U R 0 R 0 1 8 19 U R 0 R 0 1 9 0 U R 0 R 0 1 9 1 U R 0 R 0 1 9 2 U R 0 R 0 1 9 3 U R 0 R 0 1 9 4 U R 0 R 0 1 9 5 U R 0 R 0 1 9 6 U R 0 R 0 1 9 7 U R 0 R 0 1 9 8 U R 0 R 0 1 9 9 U R 0 R 0 1 9 10 U R 0 R 0 1 9 11 U R 0 R 0 1 9 12 U R 0 R 0 1 9 13 U R 0 R 0 1 9 14 U R 0 R 0 1 9 15 U R 0 R 0 1 9 16 U R 0 R 0 1 9 17 U R 0 R 0 1 9 18 U R 0 R 0 1 9 19 U R 0 R 0 1 10 0 U R 0 R 0 1 10 1 U R 0 R 0 1 10 2 U R 0 R 0 1 10 3 U R 0 R 0 1 10 4 U R 0 R 0 1 10 5 U R 0 R 0 1 10 6 U R 0 R 0 1 10 7 U R 0 R 0 1 10 8 U R 0 R 0 1 10 9 U R 0 R 0 1 10 10 U R 0 R 0 1 10 11 U R 0 R 0 1 10 12 U R 0 R 0 1 10 13 U R 0 R 0 1 10 14 U R 0 R 0 1 10 15 U R 0 R 0 1 10 16 U R 0 R 0 1 10 17 U R 0 R 0 1 10 18 U R 0 R 0 1 10 19 U R 0 R 0 1 11 0 U R 0 R 0 1 11 1 U R 0 R 0 1 11 2 U R 0 R 0 1 11 3 U R 0 R 0 1 11 4 U R 0 R 0 1 11 5 U R 0 R 0 1 11 6 U R 0 R 0 1 11 7 U R 0 R 0 1 11 8 U R 0 R 0 1 11 9 U R 0 R 0 1 11 10 U R 0 R 0 1 11 11 U R 0 R 0 1 11 12 U R 0 R 0 1 11 13 U R 0 R 0 1 11 14 U R 0 R 0 1 11 15 U R 0 R 0 1 11 16 U R 0 R 0 1 11 17 U R 0 R 0 1 11 18 U R 0 R 0 1 11 19 U R 0 R 0 1 12 0 U R 0 R 0 1 12 1 U R 0 R 0 1 12 2 U R 0 R 0 1 12 3 U R 0 R 0 1 12 4 U R 0 R 0 1 12 5 U R 0 R 0 1 12 6 U R 0 R 0 1 12 7 U R 0 R 0 1 12 8 U R 0 R 0 1 12 9 U R 0 R 0 1 12 10 U R 0 R 0 1 12 11 U R 0 R 0 1 12 12 U R 0 R 0 1 12 13 U R 0 R 0 1 12 14 U R 0 R 0 1 12 15 U R 0 R 0 1 12 16 U R 0 R 0 1 12 17 U R 0 R 0 1 12 18 U R 0 R 0 1 12 19 U R 0 R 0 1 13 0 U R 0 R 0 1 13 1 U R 0 R 0 1 13 2 U R 0 R 0 1 13 3 U R 0 R 0 1 13 4 U R 0 R 0 1 13 5 U R 0 R 0 1 13 6 U R 0 R 0 1 13 7 U R 0 R 0 1 13 8 U R 0 R 0 1 13 9 U R 0 R 0 1 13 10 U R 0 R 0 1 13 11 U R 0 R 0 1 13 12 U R 0 R 0 1 13 13 U R 0 R 0 1 13 14 U R 0 R 0 1 13 15 U R 0 R 0 1 13 16 U R 0 R 0 1 13 17 U R 0 R 0 1 13 18 U R 0 R 0 1 13 19 U R 0 R 0 1 14 0 U R 0 R 0 1 14 1 U R 0 R 0 1 14 2 U R 0 R 0 1 14 3 U R 0 R 0 1 14 4 U R 0 R 0 1 14 5 U R 0 R 0 1 14 6 U R 0 R 0 1 14 7 U R 0 R 0 1 14 8 U R 0 R 0 1 14 9 U R 0 R 0 1 14 10 U R 0 R 0 1 14 11 U R 0 R 0 1 14 12 U R 0 R 0 1 14 13 U R 0 R 0 1 14 14 U R 0 R 0 1 14 15 U R 0 R 0 1 14 16 U R 0 R 0 1 14 17 U R 0 R 0 1 14 18 U R 0 R 0 1 14 19 U R 0 R 0 1 15 0 U R 0 R 0 1 15 1 U R 0 R 0 1 15 2 U R 0 R 0 1 15 3 U R 0 R 0 1 15 4 U R 0 R 0 1 15 5 U R 0 R 0 1 15 6 U R 0 R 0 1 15 7 U R 0 R 0 1 15 8 U R 0 R 0 1 15 9 U R 0 R 0 1 15 10 U R 0 R 0 1 15 11 U R 0 R 0 1 15 12 U R 0 R 0 1 15 13 U R 0 R 0 1 15 14 U R 0 R 0 1 15 15 U R 0 R 0 1 15 16 U R 0 R 0 1 15 17 U R 0 R 0 1 15 18 U R 0 R 0 1 15 19 U R 0 R 0 1 16 0 U R 0 R 0 1 16 1 U R 0 R 0 1 16 2 U R 0 R 0 1 16 3 U R 0 R 0 1 16 4 U R 0 R 0 1 16 5 U R 0 R 0 1 16 6 U R 0 R 0 1 16 7 U R 0 R 0 1 16 8 U R 0 R 0 1 16 9 U R 0 R 0 1 16 10 U R 0 R 0 1 16 11 U R 0 R 0 1 16 12 U R 0 R 0 1 16 13 U R 0 R 0 1 16 14 U R 0 R 0 1 16 15 U R 0 R 0 1 16 16 U R 0 R 0 1 16 17 U R 0 R 0 1 16 18 U R 0 R 0 1 16 19 U R 0 R 0 1 17 0 U R 0 R 0 1 17 1 U R 0 R 0 1 17 2 U R 0 R 0 1 17 3 U R 0 R 0 1 17 4 U R 0 R 0 1 17 5 U R 0 R 0 1 17 6 U R 0 R 0 1 17 7 U R 0 R 0 1 17 8 U R 0 R 0 1 17 9 U R 0 R 0 1 17 10 U R 0 R 0 1 17 11 U R 0 R 0 1 17 12 U R 0 R 0 1 17 13 U R 0 R 0 1 17 14 U R 0 R 0 1 17 15 U R 0 R 0 1 17 16 U R 0 R 0 1 17 17 U R 0 R 0 1 17 18 U R 0 R 0 1 17 19 U R 0 R 0 1 18 0 U R 0 R 0 1 18 1 U R 0 R 0 1 18 2 U R 0 R 0 1 18 3 U R 0 R 0 1 18 4 U R 0 R 0 1 18 5 U R 0 R 0 1 18 6 U R 0 R 0 1 18 7 U R 0 R 0 1 18 8 U R 0 R 0 1 18 9 U R 0 R 0 1 18 10 U R 0 R 0 1 18 11 U R 0 R 0 1 18 12 U R 0 R 0 1 18 13 U R 0 R 0 1 18 14 U R 0 R 0 1 18 15 U R 0 R 0 1 18 16 U R 0 R 0 1 18 17 U R 0 R 0 1 18 18 U R 0 R 0 1 18 19 U R 0 R 0 1 19 0 U R 0 R 0 1 19 1 U R 0 R 0 1 19 2 U R 0 R 0 1 19 3 U R 0 R 0 1 19 4 U R 0 R 0 1 19 5 U R 0 R 0 1 19 6 U R 0 R 0 1 19 7 U R 0 R 0 1 19 8 U R 0 R 0 1 19 9 U R 0 R 0 1 19 10 U R 0 R 0 1 19 11 U R 0 R 0 1 19 12 U R 0 R 0 1 19 13 U R 0 R 0 1 19 14 U R 0 R 0 1 19 15 U R 0 R 0 1 19 16 U R 0 R 0 1 19 17 U R 0 R 0 1 19 18 U R 0 R 0 1 19 19 U R 0 R 0 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000