/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1100 点
問題文
AtCoder 市は N \times N のマス目で表されます。上から i 番目 (1 \leq i \leq N)、左から j 番目 (1 \leq j \leq N) のマスは、(i, j) と表されます。
青木君は、近日行われるマラソン大会に向けて、以下の手順からなる エクササイズ を K 回行いました。
- マス (1, 1) を出発する。
- 以下を 2N-2 回繰り返して、マス (N, N) に到着する。
- 下方向または右方向に 1 マス進む。ただし、下方向のマスと右方向のマスの両方に移動できる場合、今までのエクササイズで「そのマスを訪れた回数」が少ない方を選ぶ。同数の場合は下方向を選ぶ。
それでは、K 回目のエクササイズで通る経路を求めてください。
制約
- 2 \leq N \leq 100
- 1 \leq K \leq 10^{18}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N K
出力
長さ 2N-2 の文字列を出力してください。この i 文字目は、K 回目のエクササイズにおける i 回目の移動で下方向に動いた場合は D、右方向に動いた場合は R としてください。
入力例 1
5 4
出力例 1
RRDDRRDD
1, 2, 3, 4 回目のエクササイズでは以下の図のように動くことになります。よって、答えは RRDDRRDD です。
入力例 2
10 869120
出力例 2
RDRRRDRDRDRDRDDDRD
Score : 1100 points
Problem Statement
AtCoder City is represented by an N \times N grid. Let (i, j) denote the cell at the i‑th row from the top (1 \le i \le N) and the j‑th column from the left (1 \le j \le N).
Aoki performed the following exercise K times for marathon training.
- Start from cell (1, 1).
- Repeat the following action 2N-2 times to reach cell (N, N):
- Move one cell down or right. If both moves are possible, choose the one whose destination cell has been visited fewer times in the previous exercises. If the counts are equal, choose the downward move.
Print the path taken in the K‑th exercise.
Constraints
- 2 \le N \le 100
- 1 \le K \le 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print a string of length 2N-2. The i‑th character should be D if the i‑th move in the K‑th exercise goes downward, and R if it goes rightward.
Sample Input 1
5 4
Sample Output 1
RRDDRRDD
The 1st, 2nd, 3rd, and 4th exercises go as follows, so the answer is RRDDRRDD.
Sample Input 2
10 869120
Sample Output 2
RDRRRDRDRDRDRDDDRD