CF2253D Hypercarp and Interdimensional Jumps

Hypercarp 正驾驶着他的宇宙飞船穿越银河系的二维地图。他的飞船最初位于点 $(0, 0)$，而他想要到达的空间站位于点 $(x, y)$。 Hypercarp 的飞船配备了一台试验性的跨维发动机。其当前状态由跳跃向量 $(a, b)$ 描述：当发动机被激活时，飞船会沿第一坐标轴移动 $a$ 个单位，沿第二坐标轴移动 $b$ 个单位。最初，发动机处于完全放电状态，即 $(a, b) = (0, 0)$。 发动机以连续的周期运行。我们将每一个周期称为一次移动。在一次移动过程中，将执行以下动作： - 发动机蓄积能量，Hypercarp 必须将 $a$ 或 $b$ 的值恰好增加 $1$； - 然后，飞船从点 $(p, q)$ 跨维跳跃到 $(p + a, q + b)$。 $a$ 和 $b$ 的值不能减少。 在 Hypercarp 和空间站之间有一个安全的跨维通道。它由矩形 $[0, x] \times [0, y]$ 表示。如果飞船在任何一次跳跃后离开此矩形，就会进入不稳定的空间区域并被摧毁。 Hypercarp 可以在任意次数的跳跃后结束他的旅程。由于并非总能精确到达空间站，他希望停留在最接近 $(x, y)$ 的有效点处。 请你帮助 Hypercarp 选择移动次数和每次移动发动机参数的增加方式，使飞船停在一个合法点 $(p, q)$ 上，并且该点到空间站的欧几里得距离的平方最小。换句话说，$(p-x)^2 + (q-y)^2$ 的值应尽可能小。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 100$）。每个测试用例第一行为两个整数 $x$ 和 $y$（$1 \le x, y \le 10^8$），表示 Hypercarp 想要到达的空间站的坐标。

对于每个测试用例，输出一个由字符 $\texttt{X}$ 和 $\texttt{Y}$ 组成的字符串 $s$，描述 Hypercarp 的一条最优旅程。 字符串 $s$ 的长度等于移动次数。字符 $s_i$ 表示 Hypercarp 在第 $i$ 次移动中的操作： - 如果 $s_i = \texttt{X}$，则 Hypercarp 将 $a$ 增加 $1$，然后使用得到的向量跳跃； - 如果 $s_i = \texttt{Y}$，则 Hypercarp 将 $b$ 增加 $1$，然后使用得到的向量跳跃。 该旅程必须满足题目中的所有条件，并且最终停留在一个到空间站欧几里得距离的平方最小的点上。 可以证明，在题目限制下，每个最优解中跳跃次数不会超过 $20\,000$。如果存在多个最优解，输出其中任意一个即可。

下面给出了一些测试用例的说明。 在第一个测试用例中，字符串 $\texttt{X}$ 描述了一次移动，Hypercarp 将 $a$ 增加 $1$，然后进行如下跳跃： $$ (0, 0) \rightarrow (1, 0) $$ 飞船距离空间站 $(1, 1)$ 的距离的平方为 $1$。 在第二个测试用例中，字符串 $\texttt{XY}$ 恰好能让 Hypercarp 到达空间站： $$ (0, 0) \rightarrow (1, 0) \rightarrow (2, 1) $$ 在第三个测试用例中，字符串 $\texttt{XYX}$ 描述了以下一系列跳跃： $$ (0, 0) \rightarrow (1, 0) \rightarrow (2, 1) \rightarrow (4, 2) $$ 因此，Hypercarp 恰好到达空间站 $(4, 2)$。 在第四个测试用例中，字符串 $\texttt{XYY}$ 会使飞船停留在点 $(3, 3)$。飞船距离空间站 $(5, 4)$ 的距离的平方为 $(3-5)^2 + (3-4)^2 = 5$。 同样，也有另一组最优解，例如字符串 $\texttt{XYX}$，它会使飞船停留在点 $(4, 2)$。 由 ChatGPT 5 翻译