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_i と s_j は 0 以上 N-1 以下の一様ランダムな整数から生成される。
h_{i,j}, v_{i,j} の生成
[k]=\{0,1,\cdots,k-1\} と定義する。 N^2 個の孤立点 V=[N]\times[N] から開始し、以下の処理を行うことでグラフ G=(V,E) を作成する。
- まず、辺集合 \{\{(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} とする。
- k=0 から k=2N^2-2N-1 まで順番に、各 e_k=\{(i,j),(i',j')\} に対して、(i,j) と (i',j') が G 上で連結でないならば e_k を E に加える。
- もう一度、k=0 から k=2N^2-2N-1 まで順番に、各 e_k=\{(i,j),(i',j')\} に対して、(i,j) の次数が 1 もしくは (i',j') の次数が 1 ならば、辺 e_k を E に加える。
得られたグラフを用いて、h と v を以下のように設定する。
- h_{i,j}=0 \iff \{(i,j),(i,j+1)\}\in E
- v_{i,j}=0 \iff \{(i+1,j),(i,j)\}\in E
入力例 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 degreesF: 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.
- 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}.
- 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.
- 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)
- Local version: You need a compilation environment of Rust language.
- Web version: This is more powerful than the local version and can display animations.
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