P13384 [GCJ 2011 Finals] Program within a Program

不保证本题的 Special Judge 一定正确。

你有一个机器人，位于一条无限延伸的东西向公路上，并且它需要递送一个蛋糕。公路上每隔一英里（无论东西方向）就有一根路灯柱。你需要编程让机器人恰好向东移动 $N$ 根路灯柱，并在那里释放蛋糕。路线不必直线，只要最终机器人能在正确的位置释放蛋糕即可。 不幸的是，这个机器人只有极少的内存，并且无法进行复杂的逻辑运算。你只能在开始时给它一个非常简单的程序，这个程序必须能让它在正确的位置释放蛋糕。该程序由一条或多条语句组成，每条语句都指示机器人在特定条件下该做什么。语句格式如下： ``` -> ``` 这表示当且仅当以下所有条件满足时： 1. 机器人处于状态 $s$。 2. 机器人当前所在的路灯柱标记为 $M$。 它将执行以下动作之一： 1. 给当前路灯柱打上新标记，改变状态并移动。此时 `` 格式为 "` `"，其中 `D` 表示移动方向（'W' 表示向西，'E' 表示向东），`NS` 表示机器人的新状态，`NM` 表示当前路灯柱的新标记。 2. 在当前位置释放蛋糕并自毁。此时 `` 只需写 `release`。 如果你输出了两条或更多具有相同 $s$ 和 $M$ 的语句，机器人会出错并摧毁蛋糕。 如果机器人在某时刻处于状态 $X$，且站在标记为 $Y$ 的路灯柱上，但没有语句满足 $s=X$ 且 $M=Y$，那么机器人会困惑并吃掉蛋糕。 所有状态和标记都必须是绝对值不超过一百万（$10^6$）的整数。假设机器人初始状态为 $0$，所有路灯柱初始标记为 $0$。 给定 $N$，请编写一个程序，使机器人能在正确的位置释放蛋糕。你的程序最多只能使用 $30$ 条语句，并且必须在 $X$ 步内终止。

输入的第一行是测试用例数 $T$。接下来有 $T$ 个测试用例，每个测试用例占一行，包含一个整数 $N$，表示机器人需要释放蛋糕的路灯柱编号。

对于每个测试用例，首先输出一行 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你使用的语句条数。接下来输出 $y$ 行，每行是一条机器人程序语句，格式如上所述。 警告：评测机的响应可能比平时慢最多 5 秒，因为你的输出会作为验证的一部分运行。

**样例解释** 在第一个样例中，机器人初始状态为 $0$，路灯柱标记为 $0$。它执行唯一的语句，即释放蛋糕。 在第二个样例中，机器人有五种状态：$0$、$1$、$2$、$3$ 和 $-1$。机器人按如下方式行动： - 将当前路灯柱标记为 $1$，向东移动，进入状态 $1$。 - 将当前路灯柱标记为 $1$，向东移动，进入状态 $2$。 - 将当前路灯柱标记为 $1$，向东移动，进入状态 $3$。 - 将当前路灯柱标记为 $1$，向东移动，进入状态 $-1$。 - 释放蛋糕。 在第三个样例中，机器人有两种状态，执行如下操作： - 将当前路灯柱标记为 $1$，向东移动，进入状态 $1$。 - 将当前路灯柱标记为 $1$，向西移动，进入状态 $0$。 - 释放蛋糕。 注意，机器人两次处于状态 $0$ 时采取了不同的动作，因为它看到的标记不同。 **数据范围** - $1 \leq T \leq 15$。 **小数据集（15 分，测试点 1 - 可见）** - $0 \leq N \leq 500$。 - $X = 250,000$。 - 时间限制：30 秒。 **大数据集（23 分，测试点 2 - 隐藏）** - $0 \leq N \leq 5000$。 - $X = 150,000$。 - 时间限制：60 秒。 由 ChatGPT 4.1 翻译