A - Code Golf for Robot Vacuums Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

F社はロボット掃除機「お掃除高橋くん」を開発している。 このロボットは基礎命令と繰り返し処理のみからなる以下の形式のプログラムによって動作する。

基礎命令

  • L: 90度左を向く
  • R: 90度右を向く
  • l: 現在向いている方向が壁ならば90度左を向く
  • r: 現在向いている方向が壁ならば90度右を向く
  • F: 現在向いている方向が壁でないなら1マス前進する

繰り返し処理

基礎命令の前に正の整数値を書くと、その整数値の回数だけ基礎命令を繰り返す。 例えば、RFFFFFFFFFF というプログラムは R10F と短縮して書くことが出来る。 プログラムは()によりグループ化することが出来る。 グループの前に正の整数値を書くと、その整数値の回数だけ()内のプログラムを繰り返す。 例えば、RFRFRFLRFRFRFLというプログラムは 2(3(RF)L) と短縮して書くことが出来る。

掃除したいフロアは N\times N マスに区切られ、外周は壁に囲まれており、隣接するマスとマスの間にも壁がある場合がある。 一番左上のマスの座標を (0, 0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。 ロボットは (s_i,s_j) のマスで上方向を向いた状態から掃除を開始する。 初期位置を含め、ロボットが一度でも移動したマスは掃除済みとなる。

全てのマスを掃除できるような短いプログラムを作成してほしい。 基礎命令を1つ実行するのに1単位時間かかり、5000 単位時間以内で掃除を完了しなければならない。 出力されたプログラムが 5000 単位時間で終了しない場合は 5000 個目の基礎命令を実行後に打ち切られて停止する。 壁を向いて居ない状態で基礎命令 l もしくは r を実行した場合や、壁を向いた状態で基礎命令 F を実行した場合にも1単位時間がかかる。 5000 個目の基礎命令によって移動した先のマスも掃除済みとなる。

得点

出力されたプログラムの文字数を L、プログラムの実行が終了もしくは 5000 単位時間が経過して停止した時点で掃除済みのマスの数を M とする。 L は文字数であり、基礎命令数ではないことに注意せよ。 例えば、100(RF) というプログラムは基礎命令を 200 回実行するが、文字数は L=7 である。

  • L>10000 もしくは出力が正しい形式のプログラムで無い場合、WA と判定される。
  • M=N^2 の場合、N^2 + \mathrm{round}(10^8/(100+L)) の得点が得られる。
  • M<N^2 の場合、M の得点が得られる。

テストケースは全部で 100 個あり、各テストケースの得点の合計が提出の得点となる。 1つ以上のテストケースで AC 以外の判定がされた場合、提出の得点は0点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、その得点を獲得した提出の早い方が上位となる。


入力

入力は以下の形式で標準入力から与えられる。

s_i s_j
h_{0,0} \cdots h_{0,N-2}
\vdots
h_{N-1,0} \cdots h_{N-1,N-2}
v_{0,0} \cdots v_{0,N-1}
\vdots
v_{N-2,0} \cdots v_{N-2,N-1}

フロアの広さを表す N は、全てのテストケースで N=20 で固定である。 (s_i,s_j) はロボットの初期位置を表し、0\leq s_i, s_j\leq N-1 を満たす。

h_{i,0} \cdots h_{i,N-2}0 もしくは 1 のみからなる N-1 文字の文字列であり、(i,j)(i,j+1) のマスの間に壁がある場合は h_{i,j}=1、無い場合は h_{i,j}=0 である。 v_{i,0} \cdots v_{i,N-1}0 もしくは 1 のみからなる N 文字の文字列であり、(i,j)(i+1,j) のマスの間に壁がある場合は v_{i,j}=1、無い場合は v_{i,j}=0 である。 全てのマスは初期位置から到達可能であることが保証されている。

出力

ロボットを動かすプログラムを1行で標準出力に出力せよ。

入力生成方法

s_i, s_j の生成

s_is_j0 以上 N-1 以下の一様ランダムな整数から生成される。

h_{i,j}, v_{i,j} の生成

[k]=\{0,1,\cdots,k-1\} と定義する。 N^2 個の孤立点 V=[N]\times[N] から開始し、以下の処理を行うことでグラフ G=(V,E) を作成する。

  1. まず、辺集合 \{\{(i,j),(i,j+1)\}\mid i\in[N],j\in[N-1]\}\cup\{\{(i,j),(i+1,j)\}\mid i\in[N-1],j\in[N]\} をランダムな順番にシャッフルして e_0,\cdots,e_{2N^2-2N-1} とする。
  2. k=0 から k=2N^2-2N-1 まで順番に、各 e_k=\{(i,j),(i',j')\} に対して、(i,j)(i',j')G 上で連結でないならば e_kE に加える。
  3. もう一度、k=0 から k=2N^2-2N-1 まで順番に、各 e_k=\{(i,j),(i',j')\} に対して、(i,j) の次数が 1 もしくは (i',j') の次数が 1 ならば、辺 e_kE に加える。

得られたグラフを用いて、hv を以下のように設定する。

  • h_{i,j}=0 \iff \{(i,j),(i,j+1)\}\in E
  • v_{i,j}=0 \iff \{(i+1,j),(i,j)\}\in E

ツール(入力ジェネレータ・ビジュアライザ)

  • ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
  • Web版: ローカル版より高性能でアニメーション表示が可能です。

コンテスト終了までビジュアライズ結果の共有は禁止されています。ご注意下さい。


入力例 1

14 18
0000000000000010000
0001000001000110100
0010010001010101000
0011100000110100010
0011100000001001010
0001011000001101000
0010000000010100010
0011001000000000100
1101010010010100000
1001010110000010100
1001110101010010100
0000101000101100101
1010000100101010110
0000101100100001110
1001100100000000010
0011000100010100011
0010010000011001001
1101010011001000000
1011000001001001010
0001000101000010100
00101001010100000010
00100001100111000101
10000111000000010100
00000001011000101000
01000100011100010010
11011001101100001101
00101110101010111000
00000000101000100111
00101001011101010010
00000010000110100010
00110001010000001010
01100000110000110000
00011100000011000000
01010000101101110010
00100110001011010000
10000100101000110100
00100001100100001010
00000101001101111001
01000010000010000000

出力例 1

10(RlFlF)LFF2(3(RF)L)R10FRFR5FLFFFR4FR3FL3FR2FL2FLFFFLFFFRFFR3FRFRFFRFL2FL2FRFR2FL5FFFFFFFFFFL2FL2FR4FRFFL9FL2FRFRFFL3FL3FLFFFFFLFFL4FLFLFRFLFR2FRFRFL2FL3FLFR2FRFRFR2FLFFLFRFFR3FFFLFFFRFRFRFL2FR2FL3FRFL4FLFFR6FRFRFFFRFL4FFFLFL2FRRFL2FRR4FFRFRFR2FRFR2FLFFFR4FLFRF4FR9FRFFFFFFRFFLFL3FRFFLFL4FLFRFRFLFLFRFRFL2FLFLFLFRFR3FRFLFLLFR2FR3FFFLFFRFLFFL2FRFLFL4FLFLLFRFRFLFRF2FL4FLFRFLFLFRR2FL3FRFFRFRFLFFFRFLFLFRFFLFFLFLFR4FRFFRFRFLFFLL2FR2FFRFFFFRFRFLFR2FRFRFRFL2FFR8FR2FRFFRF2FR3FRFLFR2FRFRFL2F2FFLFLFRF2FRFL5FRFLL4FRFLFFL2FRFRFL2FRFL4FL4FLFRFFLFL2FRR3FFRFFRFRFFR2FLFL2FRFRFRFL2FL7FR2FLFFLLFL3FRFLFLFFFFFL4FLFRFLFLFFR5FL2FLFRFR3FLFL7FL2FLF2FLFL4FLFR2FL3FR2FFRFFRFRFRR3FR2FLFR11FR3FLFRFRFL2FL3FRFL2FLFLFRFL2FRFLLFL3FLFLFRFFL2FLFRFLFRFLFLFRRFRFLFL4FRFLFR2FLFLFRF2FLFRFL4FR2FLFR2FRFLFRFRFL2F

Problem Statement

F Corporation is developing a robotic vacuum cleaner, Takahashi-kun cleaner. This robot works with a program of the following form, which consists of only basic commands and repetitions.

Basic Commands

  • L: Turn left by 90 degrees.
  • R: Turn right by 90 degrees.
  • l: If the robot is facing a wall, turn left by 90 degrees.
  • r: If the robot is facing a wall, turn right by 90 degrees
  • F: If the robot is not facing a wall, move forward one square.

Repetitions

By writing a positive integer k before a basic command, the basic command will be repeated k times. For example, the program RFFFFFFFFFF can be shortened to R10F. Programs can be grouped by (). By writing a positive integer k before a group, the program in the group will be repeated k times. For example, the program RFRFRFLRFRFRFL can be shortened to 2(3(RF)L).

The floor to be cleaned is divided into N\times N squares and is surrounded by walls. There may also be walls between adjacent squares. Let (0,0) denote the top-left square, and (i,j) denote the square at the i-th row from the top and j-th column from the left. The robot starts cleaning in the square (s_i,s_j) facing upward. The robot will clean all the visited squares, including the initial position.

Your task is to output a short program that can clean all the squares. The robot takes one unit of time to execute one basic command, and the cleaning must be completed within 5000 unit of time. If the output program does not finish in 5000 unit time, it will be terminated after executing the 5000th basic command. It also takes one unit of time to execute the basic command l or r without facing the wall, or to execute the basic command F with facing the wall. The robot will also clean the square that it moves to by the 5000th basic command.

Scoring

Let L be the number of characters in the output program, and M be the number of squares that has been cleaned when the program execution is completed or terminated after 5000 unit time. Note that L is the number of characters, not the number of basic commands. For example, the program 100(RF) executes the basic commands 200 times, but the number of characters is L=7.

  • If L>10000 or your output is not a valid program, your submission will be judged as WA
  • If M=N^2, you will get a score of N^2 + \mathrm{round}(10^8/(100+L)).
  • If M<N^2, you will get a score of M.

There are 100 test cases, and the score of a submission is the total score for each test case. If you get a result other than AC for one or more test cases, the score of the submission will be zero. The highest score obtained during the contest time will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, the ranking will be determined by the submission time of the submission that received that score.


Input

Input is given from Standard Input in the following format:

s_i s_j
h_{0,0} \cdots h_{0,N-2}
\vdots
h_{N-1,0} \cdots h_{N-1,N-2}
v_{0,0} \cdots v_{0,N-1}
\vdots
v_{N-2,0} \cdots v_{N-2,N-1}

We fix N=20 for all test cases. (s_i,s_j) represents the initial position of the robot and satisfies 0\leq s_i, s_j\leq N-1.

h_{i,0} \cdots h_{i,N-2} is a string of N-1 characters consisting of only 0 or 1. If there is a wall between the squares (i,j) and (i,j+1), then h_{i,j}=1, otherwise h_{i,j}=0. v_{i,0} \cdots v_{i,N-1} is a string of N characters consisting of only 0 or 1. If there is a wall between the squares (i,j) and (i+1,j), then v_{i,j}=1, otherwise v_{i,j}=0. It is guaranteed that all squares are reachable from the initial position.

Output

Output a program to operate the robot in one line to Standard Output.

Input Generation

Generation of s_i and s_j

s_i and s_j are generated from uniform random integers between 0 and N-1, inclusive.

Generation of h_{i,j} and v_{i,j}

Let [k]=\{0,1,\cdots,k-1\}. Starting from N^2 isolated vertices V=[N]\times[N], we generate a graph G=(V,E) by the following process.

  1. First, we randomly shuffle a set of edges \{\{(i,j),(i,j+1)\}\mid i\in[N],j\in[N-1]\}\cup\{\{(i,j),(i+1,j)\}\mid i\in[N-1],j\in[N]\} and obtain an ordered edge list e_0,\cdots,e_{2N^2-2N-1}.
  2. For each e_k=\{(i,j),(i',j')\} in order from k=0 to k=2N^2-2N-1, we insert e_k into E if (i,j) and (i',j') are not connected in G.
  3. For each e_k=\{(i,j),(i',j')\} again in order from k=0 to k=2N^2-2N-1, we insert e_k into E if the degree of (i,j) is 1 or the degree of (i',j') is 1.

Using the generated graph, we generate h and v as follows.

  • h_{i,j}=0 \iff \{(i,j),(i,j+1)\}\in E
  • v_{i,j}=0 \iff \{(i+1,j),(i,j)\}\in E

Tools (Input generator and visualizer)

Sharing visualization results is not allowed until the end of the contest.


Sample Input 1

14 18
0000000000000010000
0001000001000110100
0010010001010101000
0011100000110100010
0011100000001001010
0001011000001101000
0010000000010100010
0011001000000000100
1101010010010100000
1001010110000010100
1001110101010010100
0000101000101100101
1010000100101010110
0000101100100001110
1001100100000000010
0011000100010100011
0010010000011001001
1101010011001000000
1011000001001001010
0001000101000010100
00101001010100000010
00100001100111000101
10000111000000010100
00000001011000101000
01000100011100010010
11011001101100001101
00101110101010111000
00000000101000100111
00101001011101010010
00000010000110100010
00110001010000001010
01100000110000110000
00011100000011000000
01010000101101110010
00100110001011010000
10000100101000110100
00100001100100001010
00000101001101111001
01000010000010000000

Sample Output 1

10(RlFlF)LFF2(3(RF)L)R10FRFR5FLFFFR4FR3FL3FR2FL2FLFFFLFFFRFFR3FRFRFFRFL2FL2FRFR2FL5FFFFFFFFFFL2FL2FR4FRFFL9FL2FRFRFFL3FL3FLFFFFFLFFL4FLFLFRFLFR2FRFRFL2FL3FLFR2FRFRFR2FLFFLFRFFR3FFFLFFFRFRFRFL2FR2FL3FRFL4FLFFR6FRFRFFFRFL4FFFLFL2FRRFL2FRR4FFRFRFR2FRFR2FLFFFR4FLFRF4FR9FRFFFFFFRFFLFL3FRFFLFL4FLFRFRFLFLFRFRFL2FLFLFLFRFR3FRFLFLLFR2FR3FFFLFFRFLFFL2FRFLFL4FLFLLFRFRFLFRF2FL4FLFRFLFLFRR2FL3FRFFRFRFLFFFRFLFLFRFFLFFLFLFR4FRFFRFRFLFFLL2FR2FFRFFFFRFRFLFR2FRFRFRFL2FFR8FR2FRFFRF2FR3FRFLFR2FRFRFL2F2FFLFLFRF2FRFL5FRFLL4FRFLFFL2FRFRFL2FRFL4FL4FLFRFFLFL2FRR3FFRFFRFRFFR2FLFL2FRFRFRFL2FL7FR2FLFFLLFL3FRFLFLFFFFFL4FLFRFLFLFFR5FL2FLFRFR3FLFL7FL2FLF2FLFL4FLFR2FL3FR2FFRFFRFRFRR3FR2FLFR11FR3FLFRFRFL2FL3FRFL2FLFLFRFL2FRFLLFL3FLFLFRFFL2FLFRFLFRFLFLFRRFRFLFL4FRFLFR2FLFLFRF2FLFRFL4FR2FLFR2FRFLFRFRFL2F