「RdOI R3.5 附加」ACP-II

在 1951 年，第 -32 届全国青少年信息学奥林匹克冬令营结束后，打了一上午比赛的小 A 疲惫不堪，想放松一下。于是他又借助时空传输接口（**T**ime **T**ransport **I**nterface）连接了一台 2015 年的计算机，获取到了最新的游戏「**AC** **P**roject 15 / Legacy of DWT AKing IOI」来游玩。

**这是一道传统题。** 你需要控制机器人玩躲避子弹的游戏。游戏的画面是一个在第一象限，坐标范围从 $(0,0)$ 至 $(n,m)$ 的矩形。机器人初始生成在坐标 $(0,0)$。你可以通过以下几种指令来控制这个机器人： $$ \def{\arraystretch}{1.5} \begin{array}{|c|l|}\hline \textsf{\textbf{指令}} & \textsf{\textbf{描述}} \cr\hline \bm 0 & \textsf{机器人静止不动} \cr\hline \bm 1 & \textsf{机器人向左移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x-1,y)$} \cr\hline \bm 2 & \textsf{机器人向下移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x,y-1)$} \cr\hline \bm 3 & \textsf{机器人向上移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x,y+1)$} \cr\hline \bm 4 & \textsf{机器人向右移动 $1$ 单位长度，即从 $(x,y)$ 移动到 $(x+1,y)$} \cr\hline \end{array} $$ 你构造的指令用一个数字串 $C'$ 表示。每种指令都会耗费一定的费用。具体来讲，你构造的**原始指令** $C'$ 中每包含一个 $i$ 号命令，就会耗费 $P_i$ 的费用。 你的指令会被重复 $k$ 遍，作为机器人的移动指令 $C$。例如当 $C'=1123$，$k=3$ 时，机器人收到的指令 $C= 112311231123$。 游戏中会生成 $b$ 个子弹，每个子弹用一个有序六元组 $(l_i,r_i,x_i,y_i,p_i,q_i)$ 表示。它的意思是这颗子弹在 $l_i$ 秒生成，第 $r_i$ 秒销毁。生成时的坐标为 $(x_i,y_i)$。每秒沿着 $x$ 轴正方向移动 $p_i$ 单位长度，沿着 $y$ 轴正方向移动 $q_i$ 单位长度。 游戏共进行 $d$ 秒，若 $d$ 秒内机器人碰撞到子弹或者移动到画面以外，机器人就会爆炸，游戏失败。如果在第 $d$ 秒结束时机器人没有爆炸，则游戏胜利。 游戏中的每一秒分为五个阶段，每个阶段结束后才会执行下一个阶段： 1. 机器人移动阶段。机器人会在第 $i$ 秒执行 $C_i$ 指令。若 $C$ 的长度 $< i$，也就是说所有指令都执行完了，则静止不动。 1. 子弹移动阶段，所有已经生成且还未销毁的子弹会进行一次移动。具体来讲，设当前是第 $c$ 秒，对于满足 $l_i<c\le r_i$ 的每个子弹 $(l_i,r_i,x_i,y_i,p_i,q_i)$，它的坐标会变为 $(x_i+(c-l_i)p_i,y_i+(c-l_i)q_i)$。 1. 子弹生成阶段。设当前是第 $c$ 秒，对于所有 $l_i=c$ 的子弹，将它们生成进画面，放置各自的初始位置 $(x_i,y_i)$ 上。 1. 判定阶段。若此时机器人的位置超出了画面，或者碰撞到了任意一颗已经被生成且尚未销毁的子弹，则机器人就会受击爆炸。具体来说，对于每一颗在画面上的子弹，设这颗子弹在这一秒初的位置为 $P=(x',y')$，当前的位置为 $Q=(x'',y'')$。若子弹是在这一秒内刚生成的则 $P=Q$。连接线段 $PQ$，若当前机器人的坐标在这条线段上（包括在线段的端点上），则视为机器人碰撞到了子弹。 1. 子弹销毁阶段。设当前是第 $c$ 秒，对于所有 $r_i=c$ 的子弹，将它们销毁。

- 第一行输入六个整数 $n,m,b,d,k,maxc$。 - 第二行输入五个整数 $P_0,P_1,P_2,P_3,P_4$。 - 第三行至第 $b+2$ 行，每行输入六个整数。其中第 $i+2$ 行输入的整数分别代表 $l_i,r_i,x_i,y_i,p_i,q_i$。

- 若 $maxc\ge 0$，则你需要输出一行一个字符串，表示你构造的指令，你需要保证指令费用 $\le maxc$。 - 否则，你需要输出一行一个整数，表示在所有可以成功完成游戏的指令中费用最少的指令的费用是多少。

1 1 3 100 1 5
1 1 1 2 3
1 100 0 0 1 0
1 100 1 0 0 0
2 3 0 1 0 0

34

### 样例解释 示意图里用 `0` 表示子弹，`1` 表示机器人，`.` 表示空位。 第 $1$ 秒钟：机器人移动到了 $(0,1)$；在 $(0,0)$ 和 $(1,0)$ 分别生成了一颗子弹。 ``` 1. 00 ``` 第 $2$ 秒钟：机器人移动到了 $(1,1)$；在 $(0,0)$ 处的子弹移动到了 $(0,1)$；在 $(0,1)$ 生成了一颗子弹。所以现在在 $(0,1)$ 处有两颗子弹（在下图中因为子弹重合只标出了一颗）。 ``` 01 .0 ``` 第 $3$ 秒钟：机器人位置不变；其中一颗位于 $(0,1)$ 的子弹飞出了画面；另外一颗位于 $(0,1)$ 的子弹被销毁。 ``` .1 .0 ``` 第 $4$ 秒至第 $100$ 秒：机器人没有移动；位于画面外的子弹移动后仍然在画面之外，在画面内的那颗子弹没有移动，画面情况同第三秒的情况。 综上所述，这个指令可以成功完成游戏，费用为 $1\times 3+ 1 \times2=5$。 --- ### 数据范围及限制 **本题采用捆绑测试。** $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|c|}\hline \textbf{subtask} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\cr\hline \textbf{分值} & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15\cr\hline \end{array} $$ 对于 $100\%$ 的数据，保证 $n,m,b,d,P_i\ge0$，$k\ge 1$，$1\le l \le r$，$maxc\ge-1$。 你可能会想，这算什么数据范围？怎么没有上界？而且表格里怎么没有 subtask 的特殊限制？实际上，出题人也不知道数据的上界和特殊限制。 由于出题人的误操作，数据生成器源代码意外丢失，只剩下可执行程序。下发文件中提供了在 Windows / Linux / Mac 下编译的可执行程序。不同操作系统下编译的文件名如下： - 对于 Windows 系统（文件名 genX-w32）：`g++ genX.cpp -o genX -O3 -std=c++14`，在 Windows10，Dev-C++ 5.50，TDM-GCC 4.9.2 32bit 下编译。 - 对于 Linux/Mac 系统（32 位，文件名 genX-l32）：`g++ genX.cpp -o genX -O3 -std=c++14 -m32`，在 NOI Linux 2.0，GCC 9.3.0 下编译。 - 对于 Linux/Mac 系统（64 位，文件名 genX-l64）：`g++ genX.cpp -o genX -O3 -std=c++14 -m64`，在 NOI Linux 2.0，GCC 9.3.0 下编译。 数据生成器需要在运行后输入一个 $[1,2^{30})$ 范围内的整数作为随机数种子，它会生成一份输入至 `0.in` 中。出题人无法保证生成的数据范围，但是可以保证： - 同一个生成器所生成出的数据拥有同一个特殊限制。 - 所有生成器在 NOI Linux 2.0，处理器 i5-4200m 下运行，所用时间不超过 3s，内存占用不超过 2G。 - 生成出来的数据只与你输入的种子有关，与当前时间、操作系统等其它可变因素无关。 - 部分数据生成器会有极小概率生成一个无解数据，但保证 OJ 上的所有数据均有解。 - 你输入的种子只会当作随机数的种子使用，生成器不会出现特判种子生成干扰数据等行为。 数据中的每个 subtask 分别对应一个数据生成器所生成的数据。编号为 $X$ 的 subtask 对应的生成器是 `genX`。 **注意：由于输入格式中没有要求输入「subtask 编号」，你需要自己判断当前数据所对应的 subtask。且本题的 subtask 为乱序排布，你需要自己判断每个 subtask 的难易程度。** 同时，在下发文件分发有 `checker.cpp`。使用 `g++ checker.cpp -o checker -std=c++14` 将 `checker.cpp` 编译为可执行文件后运行 `./checker <inputfile> <outputfile>`，`checker` 就会给出游戏的输赢情况。其中 `<inputfile>` 为数据生成器生成的 `.in` 文件；`<outputfile>` 中存放你的输出。**本 checker 仅供理解游戏规则使用，和实际使用的 checker 有所不同，且不保证 checker 的时间复杂度正确。**