CF637D Running with Obstacles

一名运动员从坐标 $x_{start}=0$ 出发，沿一条直线跑向坐标为 $x_{finish}=m$ 的终点。此外，运动员可以跳跃——他可以在前方不少于 $s$ 米没有障碍的情况下助跑 $s$ 米，然后最多跳跃 $d$ 米。跑步和跳跃只能朝从左到右的方向进行。他可以在没有障碍的整数坐标点开始和结束跳跃。若要越过某个障碍，必须在该障碍右侧的某个位点落地。 运动员前方有 $n$ 个障碍物，分别位于 $x_{1},x_{2},...,x_{n}$ 位置。他不能踩到障碍物上，只能跳过去。你的任务是判断运动员能否到达终点。

输入第一行包含四个整数 $n$、$m$、$s$ 和 $d$（$1\leq n\leq 200000$，$2\leq m\leq 10^{9}$，$1\leq s,d\leq 10^{9}$），分别表示障碍物的数量、终点坐标、跳跃前需要的最小助跑距离和最大跳跃距离。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1\leq a_{i}\leq m-1$），表示障碍物所在的坐标。保证起点和终点没有障碍，而且任意一个点至多有一个障碍物。障碍物坐标顺序随机。

如果不能到达终点，则第一行输出 “IMPOSSIBLE”。 如果能到达终点，输出任意一组到达终点的移动方案，格式如下： - 若运动员应往前跑 $X$ 米，则输出一行："RUN X"（$X$ 为正整数）； - 若运动员应跳跃 $Y$ 米，则输出一行："JUMP Y"（$Y$ 为正整数）。 所有的 “RUN” 和 “JUMP” 命令须严格交替，且以 “RUN” 开头，按时间先后顺序输出。不允许跳跃超过终点，但可以恰好落在终点。只需到达终点即可停止。

由 ChatGPT 5 翻译