#P18089. Yesterday Once More (Easy Version)

Yesterday Once More (Easy Version)

题目描述

Yuki 生活在一个有 n+1n+1 行、nn 列的网格中。行从上到下依次编号为 1,2,…,n+11,2,\ldots,n+1,列从左到右依次编号为 1,2,…,n1,2,\ldots,n。用 (i,j)(i,j) 表示第 ii 行、第 jj 列的格子。

网格中共有 n−1n-1 个障碍物,并且满足:

  1. 第 11 行和第 n+1n+1 行没有障碍物。
  2. 对所有 2≤i≤n2\le i\le n,第 ii 行恰好有一个障碍物。
  3. 对所有 1≤j≤n1\le j\le n,第 jj 列至多有一个障碍物。

开始时,Yuki 位于 (1,1)(1,1)。她听说第 n+1n+1 行生活着一群袋鼠,因此想前往第 n+1n+1 行看风景。

Yuki 可以按给定指令移动。每条指令指定上、下、左、右中的一个方向,她尝试沿该方向移动一格:

  • 如果目标格子在网格内且没有障碍物,就移动到目标格子;
  • 否则,这次移动无效,Yuki 留在原地。

遗憾的是,Yuki 不知道障碍物的具体位置,只知道上面的三条摆放规则。

请构造一串固定的移动指令,使得对于任意一种满足条件的障碍物分布,Yuki 在执行这一整串指令的过程中,至少有一次到达第 n+1n+1 行。

注意:只要求她在某个时刻到达过最后一行,不要求执行完全部指令后仍停留在那里。

简单版要求指令总数不超过 30n30n。

输入格式

输入只有一行,包含一个整数 nn。

输出格式

第一行输出整数 kk,表示指令总数,要求满足 1≤k≤30n1\le k\le30n。

第二行输出一个长度恰好为 kk 的字符串 ss,仅包含以下四种字符:

字符 操作
U 向上移动一格
D 向下移动一格
L 向左移动一格
R 向右移动一格

如果有多个符合要求的答案,输出任意一个即可。

数据范围

对于所有测试数据,2≤n≤1032\le n\le10^3。

样例 1

输入

2

输出

4
DRDD

样例 2

输入

3

输出

17
DDDUUURDDDUUURDDD

样例解释

在样例 1 中,网格为 3×23\times2,只有第 22 行有一个障碍物,因此仅有两种合法摆法。用 # 表示障碍物,用 . 表示空格:

情况一:

..
#.
..

执行 DRDD 时,Yuki 依次位于

$$(1,1)\rightarrow(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(3,2)$$

情况二:

..
.#
..

执行 DRDD 时,Yuki 依次位于

$$(1,1)\rightarrow(2,1)\rightarrow(2,1)\rightarrow(3,1)\rightarrow(3,1)$$

两种情况下都能到达第 33 行,所以这个答案合法。

样例 2 中,共有 3!=63!=6 种合法障碍物分布;给出的指令序列在这六种情况下均能到达第 44 行。