AdditionalFile5558.zip

#5558. 「POI2026 R1」Łazik kosmiczny

标签: 传统 | 时间限制: 6000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – I etap Łazik kosmiczny

官方提供了可视化工具：https://oi.edu.pl/l/33oi_laz

Bajtazar 发现了一颗环面（torus）形状的行星。行星表面被划分为 $n$ 行 $m$ 列的网格，行号从 $0$ 到 $n-1$，列号从 $0$ 到 $m-1$，格子坐标记作 $(x,y)$。

为了探索这颗行星，将派遣一辆宇宙漫游车，从坐标 $(0,0)$ 出发，按照一条指令序列不断移动。

漫游车能够识别以下四种指令：

• G —— 向上走一步：从 $(x,y)$ 移动到 $((x-1) \bmod n, y)$
• D —— 向下走一步：从 $(x,y)$ 移动到 $((x+1) \bmod n, y)$
• L —— 向左走一步：从 $(x,y)$ 移动到 $(x, (y-1) \bmod m)$
• P —— 向右走一步：从 $(x,y)$ 移动到 $(x, (y+1) \bmod m)$

漫游车会无限循环执行你给出的整条指令序列：执行完最后一条指令后，立刻从头开始重新执行。

要求：最终漫游车必须访问到行星上全部 $n \times m$ 个格子（允许重复访问某些格子）。

请你构造一条尽可能短（但不要求绝对最短）的指令序列，使其满足上述条件。

输入格式

仅一行两个整数 $n, m$ $(2 \leq n, m \leq 10^6)$，表示行数和列数。

输出格式

第一行输出一个正整数 $k$，表示你构造的指令序列长度。

第二行输出长度为 $k$ 的字符串，仅由字符 G、D、L、P 组成。

样例 1

输入

2 3

输出

3
DPD

运行轨迹（从 $(0,0)$ 开始）：

$$(0,0) \xrightarrow{\mathrm{D}}(1,0) \xrightarrow{\mathrm{P}}(1,1) \xrightarrow{\mathrm{D}}(0,1) \xrightarrow{\mathrm{D}}(1,1) \xrightarrow{\mathrm{P}}(1,2) \xrightarrow{\mathrm{D}}(0,2) \xrightarrow{\mathrm{D}}(1,2) \xrightarrow{\mathrm{P}}(1,0) \xrightarrow{\mathrm{D}}(0,0) \xrightarrow{\mathrm{D}} \ldots$$

附加样例

1. $n=5, m=4$，可以使用 $\texttt{PPPDDDLLGPGLLDDDPPP}$ 等序列覆盖全部格子
2. $n=1000, m=1000$，可以使用 $(\texttt{DP})^{1234567}\texttt{GGL}$ 等序列覆盖全部格子

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n, m \leq 6$	$11$
$2$	$n, m \leq 20$	$20$
$3$	$n \leq 10^3,\ n=2m+3$	$13$
$4$	$n \leq 10^3,\ m \leq 20$	$12$
$5$	$n, m \leq 10^3$	$24$
$6$	$n, m \leq 10^4$	$7$
$7$	$n, m \leq 10^5$	$7$
$8$	无附加限制	$6$

设你输出的序列长度为 $k$，该测试点的最优序列长度为 $OPT$，你将得到的分数为

$$\left\lfloor \frac{100}{\sqrt{1 + k - OPT}} \right\rfloor$$

即序列越接近最优，分数越高。即使 $k$ 很大，只要能覆盖全图仍可拿到基础分数。