/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
ストーリー
F社はロボット掃除機「お掃除高橋くん2号」を開発し、F社のオフィスの掃除を任せることにした。 お掃除高橋くん2号は、太陽光発電により永久に動き続けることが出来、決められたルートでの掃除を無限に繰り返す。 オフィスは場所によって汚れやすさが異なり、汚れやすい場所を頻繁に掃除することで、オフィス全体をより綺麗に保つことが出来る。 オフィスを出来るだけ綺麗に保つことが出来るような掃除ルートを決定して欲しい。
問題文
N\times N マスの盤面がある。 一番左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。 N\times N マスの外周は壁で囲われており、上下左右に隣接するマス間にも壁がある場合がある。
各マス (i, j) には汚れやすさ d_{i,j} が定まっており、盤面上を移動することで掃除を行う。 壁で遮られていない隣接マスに移動することが出来、移動後に移動先のマスの汚れは 0 となり、それ以外の全てのマス (i,j) の汚れは d_{i,j} 増加する。 (0, 0) からスタートして、(0, 0) に戻ってくるような、長さ(移動回数) 10^5 以下の掃除ルートを考える。 掃除ルートは同じマスを何度でも通って良いが、一度も通らないマスがあってはならない。
t 回目の移動後の各マス (i,j) の汚れを a_{t,i,j} とし、汚れの総和を S_t=\sum_{i=0}^{N-1}\sum_{j=0}^{N-1} a_{t,i,j} と表す。 t=0 において、全てのマスの汚れは a_{0,i,j}=0 であるとする。 長さ L の掃除ルートでの掃除を無限に繰り返したとき、t=L,L+1,\cdots,2L-1 の間の汚れの総和の平均値 \[ \bar{S}=\frac{1}{L}\sum_{t=L}^{2L-1}S_t \] を平均汚れと定義する。
平均汚れが出来るだけ小さくなるような掃除ルートを求めて欲しい。
平均汚れの意味について
長さ L の掃除ルートでの掃除を無限に繰り返した時、t\geq L に対して、a_{t,i,j}=a_{t+L,i,j} が成り立つことが証明出来る。 従って、Tターン目までの汚れの総和の平均値 \frac{1}{T} \sum_{t=0}^{T-1} S_t を考えると、その T \to \infty での極限が平均汚れと一致する。
得点
出力した掃除ルートにおける平均汚れを \bar{S} としたとき、\mathrm{round}(\bar{S}) の絶対スコアが得られる。絶対スコアは小さければ小さいほど良い。 不正な掃除ルート(長さが 10^5 を越える、(0,0) に戻ってこない、一度も通らないマスが存在する、壁にぶつかる)が出力された場合は WA と判定される。
各テストケース毎に、\mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) の相対評価スコアが得られ、その和が提出の得点となる。
最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストは CE 以外の結果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。
テストケース数
- 暫定テスト: 50個
- システムテスト: 2000個、コンテスト終了後に seeds.txt (sha256=cdea33a6050850bf1387e2191b802a1df7e43fcb969fd6c3bf9cbd96a4d790d7) を公開
相対評価システムについて
暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。
順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。
実行時間について
実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。
入力
入力は以下の形式で標準入力から与えられる。
N
h_{0,0}\cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
d_{0,0} \cdots d_{0,N-1}
\vdots
d_{N-1,0} \cdots d_{N-1,N-1}
- N は盤面の縦横の大きさを表し、20\leq N\leq 40 を満たす。
- h_{i,0}\cdots h_{i,N-1} は
0と1からなる N 文字の文字列であり、h_{i,j}=1 であればマス (i,j) とその下隣のマス (i+1,j) の間に壁があり、h_{i,j}=0 であれば壁がないことを表す。 - v_{i,0}\cdots v_{i,N-2} は
0と1からなる N-1 文字の文字列であり、v_{i,j}=1 であればマス (i,j) とその右隣のマス (i,j+1) の間に壁があり、v_{i,j}=0 であれば壁がないことを表す。 - 全てのマスは (0, 0) から到達可能であることが保証されている。
- d_{i,j} はマス (i,j) の汚れやすさを表す整数値で、1\leq d_{i,j}\leq 10^3 を満たす。
出力
上下左右への移動をそれぞれ U, D, L, R で表す。
長さ L の掃除ルートを対応する文字を繋げた L 文字の文字列で表し、一行で標準出力に出力せよ。
サンプルプログラム
import sys
sys.setrecursionlimit(1000000)
N = int(input()) h = [input() for _ in range(N-1)] v = [input() for _ in range(N)] d = [list(map(int, input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)] DIJ = [(0, 1), (1, 0), (0, -1), (-1, 0)] DIR = "RDLU"
def dfs(i, j): visited[i][j] = True for dir in range(4): di, dj = DIJ[dir] i2 = i + di j2 = j + dj if 0 <= i2 < N and 0 <= j2 < N and not visited[i2][j2]: if di == 0 and v[i][min(j, j2)] == '0' or dj == 0 and h[min(i, i2)][j] == '0': print(DIR[dir], end='') dfs(i2, j2) print(DIR[(dir + 2) % 4], end='')
dfs(0, 0) print()
入力生成方法
N の生成
N=\mathrm{randint}(20,40) と生成する。
h, v の生成
壁の多さを決めるパラメータ w=\mathrm{randint}(1,N) を生成する。 壁が全く無い状態から始め、以下の操作を w 回繰り返すことで壁を生成する。
上下左右の四方向からランダムに1つ選択する。 左方向の場合、i=\mathrm{randint}(0,N-2)、j=\mathrm{randint}(0,N-1)、k=\mathrm{randint}(3,\lfloor N/2\rfloor) を生成し、h_{i,j}\cdots h_{i,\max(j-k+1, 0)} を 1 にする。 右方向の場合も同様に生成して、h_{i,j}\cdots h_{i,\min(j+k-1, N-1)} を 1 にする。 上方向の場合、i=\mathrm{randint}(0,N-1)、j=\mathrm{randint}(0,N-2)、k=\mathrm{randint}(3,\lfloor N/2\rfloor) を生成し、v_{i,j}\cdots v_{\max(i-k+1, 0),j} を 1 にする。 下方向の場合も同様に生成して、v_{i,j}\cdots v_{\min(i+k-1,N-1),j} を 1 にする。
w 回の繰り返しが完了したら、全てのマスが (0, 0) から到達可能であるかを判定し、到達不能なマスがある場合は壁を全て除去して w 回の繰り返し処理をやり直す。
d の生成
汚れやすい領域の数を決めるパラメータ c=\mathrm{randint}(1,\lfloor N/2\rfloor) を生成する。 全ての (i,j) について d'_{i,j}=0 である配列 d' を用意し、以下の処理を c 回繰り返すことで d' を更新する。
i=\mathrm{randint}(0,N-1)、j=\mathrm{randint}(0,N-1)、m=\mathrm{randint}(N,\lfloor N^2/c\rfloor)、b=\mathrm{randdouble}(0,2) を生成する。 集合 S を S=\{(i,j)\} から開始して、S の大きさが m になるまで以下の処理を繰り返すことで生成する。
p\in S をランダムに選び、上下左右の方向をランダムに選ぶ。p からその方向に壁が無い場合、隣接マス q を S に追加する。
生成した S に含まれる各マス (i',j')\in S に対して、d'_{i',j'}=b と上書きする。
c 回の繰り返し処理が完了したら、各 (i,j) について、d_{i,j}=\mathrm{round}(10^{d'_{i,j}+\mathrm{randdouble}(0,1)}) と生成する。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
入力例 1
20 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 251 348 2 2 5 4 14 13 13 43 7 10 8 36 11 10 3 5 1 6 179 68 3 7 6 13 25 25 30 26 13 6 16 11 20 9 1 5 10 1 135 42 1 1 4 3 2 39 24 20 51 13 29 47 8 21 4 2 2 3 57 138 133 46 4 4 7 18 26 6 17 43 29 48 10 21 2 8 3 1 148 77 220 100 127 2 3 8 41 9 19 14 17 1 2 1 2 1 2 3 237 65 193 245 244 10 1 2 7 20 5 5 4 6 4 5 4 8 2 2 107 73 85 176 1 5 6 22 11 17 4 12 20 5 1 3 8 2 7 4 262 201 56 4 9 9 6 2 2 1 20 25 8 1 1 4 1 3 3 6 3 93 1 3 1 6 4 5 7 4 3 29 17 18 9 2 6 9 2 5 68 184 236 102 3 2 2 4 16 20 5 26 21 19 124 276 1 11 39 2 5 4 2 3 8 1 4 2 6 16 3 7 25 17 5 501 172 5 279 8 1 4 5 6 7 5 3 2 1 4 9 7 245 151 6 4 10 2 78 13 2 4 4 9 6 4 2 4 8 4 4 14 17 657 15 3 4 10 474 9 7 3 9 3 1 2 2 2 4 2 3 8 15 7 12 9 8 7 5 630 2 1 2 4 3 1 3 1 3 7 4 4 8 8 10 3 4 10 203 220 3 6 9 1 2 4 6 2 3 2 1 40 24 6 3 8 4 7 248 287 6 6 1 4 2 8 2 7 3 6 4 3 1 12 12 3 11 16 85 222 7 6 2 7 2 5 2 5 4 8 2 6 1 5 9 2 4 7 1 8 3 2 9 3 2 2 6 2 3 5 2 4 7 3 5 11 7 128 7 5 4 3 4 9 1 1 4 3 4 3 3 5 1 1 2 18 9 2 9 6
出力例 1
RRRRRRRRRRRRRRRRRRRDDDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRULLLLURRRRULLLLURRRRULLLLURRRRURRRRRRRRRRRRRRDDDDDDDLLLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRRUUUUUUUULLLLLLLLLLLLLLLDLLLURRURRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLRRDLLDRRRURRRRRRRRRRRRRRRDLLLLLLLLLLLLLLDLLLLDRRRRDLLLLDRRRRDLLLLDRRRRDLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLL
Story
F Corporation developed a robotic vacuum cleaner, Takahashi-kun cleaner No.2, and decided to entrust it with the cleaning of their office. Takahashi-kun cleaner No.2 can operate indefinitely through solar power and repeats cleaning on a predetermined route indefinitely. The office has varying levels of susceptibility to dirt in different areas, and by frequently cleaning the areas that are more prone to dirt, the entire office can be kept cleaner.
Problem Statement
There is an N\times N square board. Let (0, 0) be the coordinates of the top-left square, and (i, j) be the coordinates of the square located i squares down and j squares to the right from there. The perimeter of the N\times N board is surrounded by walls, and there may also be walls between adjacent squares.
Each square (i,j) is assigned a value d_{i,j} which represents its susceptibility to dirt. Your task is to clean these squares by moving around the board. You can move to an adjacent square that is not blocked by a wall. After the move, the dirtiness of the square you moved to becomes 0, and the dirtiness of all other squares (i, j) increases by d_{i, j}. Consider a cleaning route that starts and ends at (0, 0), with a length (number of moves) not exceeding 10^5. The cleaning route may pass through the same square multiple times, but must visit each square at least once.
Let a_{t,i,j} denote the dirtiness of each square (i,j) after the t-th move, and let S_t=\sum_{i=0}^{N-1}\sum_{j=0}^{N-1} a_{t,i,j} denote the total dirtiness. At t=0, we assume that the dirtiness of all squares is a_{0,i,j}=0. Define the average dirtiness as \[ \bar{S}=\frac{1}{L}\sum_{t=L}^{2L-1}S_t, \] which is the average of the total dirtiness during the period t=L,L+1,\cdots,2L-1 when the cleaning route of length L is repeated infinitely.
Please find a cleaning route that minimizes the average dirtiness as much as possible.
The Meaning of Average Dirtiness
We can prove that a_{t,i,j}=a_{t+L,i,j} for t\geq L when the cleaning route of length L is repeated infinitely. Therefore, considering the average \frac{1}{T} \sum_{t=0}^{T-1} S_t of the total dirtiness up to T turns, its limit as T \to \infty coincides with the average dirtiness.
Scoring
Let \bar{S} be the average dirtiness of the output cleaning route. Then you will obtain an absolute score of \mathrm{round}(\bar{S}). The lower the absolute score, the better. If you output an illegal cleaning route (length exceeds 10^5, does not return to (0,0), there is an unvisited square, or it hits a wall), it will be judged as WA.
For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.
The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.
The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.
Number of test cases
- Provisional test: 50
- System test: 2000. We will publish seeds.txt (sha256=cdea33a6050850bf1387e2191b802a1df7e43fcb969fd6c3bf9cbd96a4d790d7) after the contest is over.
About relative evaluation system
In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.
The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.
About execution time
Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.
Input
Input is given from Standard Input in the following format.
N
h_{0,0}\cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
d_{0,0} \cdots d_{0,N-1}
\vdots
d_{N-1,0} \cdots d_{N-1,N-1}
- N is the horizontal and vertical size of the board and satisfies 20\leq N\leq 40.
- h_{i,0}\cdots h_{i,N-1} is a string of length N consisting of only
0and1. h_{i,j}=1 if and only if there is a wall between square (i,j) and its lower neighbor (i+1,j). - v_{i,0}\cdots v_{i,N-2} is a string of length N-1 consisting of only
0and1. v_{i,j}=1 if and only if there is a wall between square (i,j) and its right neighbor (i,j+1). - All squares are guaranteed to be reachable from (0, 0).
- d_{i,j} is an integer value representing the susceptibility to dirt of square (i,j) and satisfies 1\leq d_{i,j}\leq 10^3.
Output
Represent a move up, down, left, or right by U, D, L, or R, respectively.
Represent the cleaning route of length L as a string of L characters corresponding to each move, and output it in a single line to Standard Output.
Sample Solution
import sys
sys.setrecursionlimit(1000000)
N = int(input()) h = [input() for _ in range(N-1)] v = [input() for _ in range(N)] d = [list(map(int, input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)] DIJ = [(0, 1), (1, 0), (0, -1), (-1, 0)] DIR = "RDLU"
def dfs(i, j): visited[i][j] = True for dir in range(4): di, dj = DIJ[dir] i2 = i + di j2 = j + dj if 0 <= i2 < N and 0 <= j2 < N and not visited[i2][j2]: if di == 0 and v[i][min(j, j2)] == '0' or dj == 0 and h[min(i, i2)][j] == '0': print(DIR[dir], end='') dfs(i2, j2) print(DIR[(dir + 2) % 4], end='')
dfs(0, 0) print()
Input Generation
Generation of N
N=\mathrm{randint}(20,40).
Generation of h and v
Generate a parameter w=\mathrm{randint}(1,N) that controls the number of walls. Starting from a state with no walls, generate walls by repeating the following operation w times.
Randomly select one of the four directions (up, down, left, right). For the left direction, generate i=\mathrm{randint}(0,N-2), j=\mathrm{randint}(0,N-1), and k=\mathrm{randint}(3,\lfloor N/2\rfloor). Then, set h_{i,j}\cdots h_{i,\max(j-k+1, 0)} to 1. Similarly, for the right direction, generate values in the same manner, and set h_{i,j}\cdots h_{i,\min(j+k-1, N-1)} to 1. For the upward direction, generate i=\mathrm{randint}(0,N-1), j=\mathrm{randint}(0,N-2), and k=\mathrm{randint}(3,\lfloor N/2\rfloor). Then, set v_{i,j}\cdots v_{\max(i-k+1, 0),j} to 1. Similarly, for the downward direction, generate values in the same manner, and set v_{i,j}\cdots v_{\min(i+k-1, N-1),j} to 1.
After w iterations are completed, check if all squares are reachable from (0, 0), and if there are unreachable squares, remove all walls and redo the w iterations.
Generation of d
Generate a parameter c=\mathrm{randint}(1,\lfloor N/2\rfloor) that determines the number of susceptible regions. Create an array d' with d'_{i,j}=0 for all (i,j), and update d' by repeating the following process c times.
Generate i=\mathrm{randint}(0,N-1), j=\mathrm{randint}(0,N-1), m=\mathrm{randint}(N,\lfloor N^2/c\rfloor), and b=\mathrm{randdouble}(0,2). Generate a set S by starting from S=\{(i,j)\} and repeating the following process until the size of S becomes m.
Randomly choose p\in S, and randomly choose one of the four directions (up, down, left, or right). If there is no wall in that direction from p, add the adjacent square q to S.
For each square (i',j')\in S contained in the generated S, overwrite d'_{i',j'}=b.
After c iterations are completed, generate d_{i,j}=\mathrm{round}(10^{d'_{i,j}+\mathrm{randdouble}(0,1)}) for each (i,j).
Tools (Input generator and visualizer)
- Web version: This is more powerful than the local version providing animations.
- 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 during the contest is prohibited.
Sample Input 1
20 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000100000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 0000000000000000000 251 348 2 2 5 4 14 13 13 43 7 10 8 36 11 10 3 5 1 6 179 68 3 7 6 13 25 25 30 26 13 6 16 11 20 9 1 5 10 1 135 42 1 1 4 3 2 39 24 20 51 13 29 47 8 21 4 2 2 3 57 138 133 46 4 4 7 18 26 6 17 43 29 48 10 21 2 8 3 1 148 77 220 100 127 2 3 8 41 9 19 14 17 1 2 1 2 1 2 3 237 65 193 245 244 10 1 2 7 20 5 5 4 6 4 5 4 8 2 2 107 73 85 176 1 5 6 22 11 17 4 12 20 5 1 3 8 2 7 4 262 201 56 4 9 9 6 2 2 1 20 25 8 1 1 4 1 3 3 6 3 93 1 3 1 6 4 5 7 4 3 29 17 18 9 2 6 9 2 5 68 184 236 102 3 2 2 4 16 20 5 26 21 19 124 276 1 11 39 2 5 4 2 3 8 1 4 2 6 16 3 7 25 17 5 501 172 5 279 8 1 4 5 6 7 5 3 2 1 4 9 7 245 151 6 4 10 2 78 13 2 4 4 9 6 4 2 4 8 4 4 14 17 657 15 3 4 10 474 9 7 3 9 3 1 2 2 2 4 2 3 8 15 7 12 9 8 7 5 630 2 1 2 4 3 1 3 1 3 7 4 4 8 8 10 3 4 10 203 220 3 6 9 1 2 4 6 2 3 2 1 40 24 6 3 8 4 7 248 287 6 6 1 4 2 8 2 7 3 6 4 3 1 12 12 3 11 16 85 222 7 6 2 7 2 5 2 5 4 8 2 6 1 5 9 2 4 7 1 8 3 2 9 3 2 2 6 2 3 5 2 4 7 3 5 11 7 128 7 5 4 3 4 9 1 1 4 3 4 3 3 5 1 1 2 18 9 2 9 6
Sample Output 1
RRRRRRRRRRRRRRRRRRRDDDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRRRRRRRRRRRRRRRULLLLLLLLLLLLLLLLLLURRRRULLLLURRRRULLLLURRRRULLLLURRRRURRRRRRRRRRRRRRDDDDDDDLLLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLURRRRRRRRRRRRULLLLLLLLLLLLRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRDLLLLLLLLLLLLDRRRRRRRRRRRRRUUUUUUUULLLLLLLLLLLLLLLDLLLURRURRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLRRDLLDRRRURRRRRRRRRRRRRRRDLLLLLLLLLLLLLLDLLLLDRRRRDLLLLDRRRRDLLLLDRRRRDLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRDLLLLLLLLLLLLLLLLLLDRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLL