← 返回题目列表

Codeforces · 1817/D

D. 玩具机

中文机器翻译题面 查看原题

有一台玩具机,玩具排列成两排,每排 $$$n$$$ 个单元格($$$n$$$ 为奇数)。

$$$n=9$$$ 的初始状态。

最初,$$$n-2$$$ 玩具被放置在顶行的非角单元中。底行最初是空的,其最左边、最右边和中央的单元格被阻挡。有 $$$4$$$ 按钮来控制玩具机器:左、右、上、下,分别用字母 L、R、U 和 D 标记。

当按下 L、R、U 或 D 时,所有玩具将同时向相应方向移动,并且只有在推入另一个玩具、墙壁或堵塞的单元格时才会停止。您的目标是将第 $$$k$$$ 个玩具移到顶行最左边的单元格中。玩具从左到右编号为 $$$1$$$ 到 $$$n-2$$$。给定 $$$n$$$ 和 $$$k$$$,找到最多使用 $$$1\,000\,000$$$ 按钮按下的解决方案。

为了测试玩具机,可以使用一个网页来实时玩游戏。

输入

第一行也是唯一一行包含两个整数,$$$n$$$ 和 $$$k$$$($$$5 \le n \le 100\,000$$$,$$$n$$$ 为奇数,$$$1 \le k \le n-2$$$)— 一行中的单元格数量,以及必须移动到顶行最左边单元格的玩具的索引。

输出

在一行上,将按钮按下的描述输出为最多 $$$1\,000\,000$$$ 个字符的字符串。该字符串应仅包含字符 L、R、U 和 D。字符串中的第 $$$i$$$ 字符是按下的第 $$$i$$$ 按钮。按下所有按钮后,第 $$$k$$$ 个玩具应位于顶行最左边的单元格中。

如果有多个解决方案,请打印其中一个。不必尽量减少按下按钮的次数。

示例

输入 #1

5 1

输出 #1

RDL

输入 #2

7 2

输出 #2

RDL

注意

在第一个示例中,将有 $$$5-2 = 3$$$ 玩具。第一个玩具需要位于顶行最左边的单元格中。 RDL 将实现这一点的动作,请参见图片以便更好地理解。另一种可能的解决方案是按 L 键。

第一个示例的动作可视化。