AT_agc072_c [AGC072C] Human Exercise
题目描述
AtCoder 市被表示为 $N \times N$ 的网格。从上往下第 $i$ 行（$1 \leq i \leq N$）、从左往右第 $j$ 列（$1 \leq j \leq N$）的格子记作 $(i, j)$。
青木君为了即将到来的马拉松比赛，进行了 $K$ 次如下步骤组成的“锻炼”：
1. 从格子 $(1, 1)$ 出发。
2. 重复以下操作 $2N-2$ 次，最终到达格子 $(N, N)$：
- 向下或向右移动 $1$ 格。如果可以同时向下和向右移动，则选择“在之前所有锻炼中被访问次数较少”的格子。如果次数相同，则优先选择向下。
请你求出第 $K$ 次锻炼时经过的路径。
输入格式
输入从标准输入中给出，格式如下：
> $N$ $K$
输出格式
输出一个长度为 $2N-2$ 的字符串。第 $i$ 个字符表示第 $K$ 次锻炼的第 $i$ 步：若向下移动则为 `D`，若向右移动则为 `R`。
说明/提示
## 限制
- $2 \leq N \leq 100$
- $1 \leq K \leq 10^{18}$
- 输入的所有数均为整数
## 样例解释 1
第 $1, 2, 3, 4$ 次锻炼时的移动如下图所示。因此，答案为 `RRDDRRDD`。
由 ChatGPT 4.1 翻译