P16347 Wisdom, Computer Science, and the E.T.C.

本题出处：https://www.luogu.com.cn/contest/314899 :::warning{open} 由于出题人赶着出题，本题大部分内容可能会比较简单。 如果你秒了的话，可以出出加强版。 ::: ::::info[广告] There are many types of companies that can transport things. For example, some of them can transport food, we call them food transportation companies. Similarly, there are material transportation companies, factory transportation companies, furniture transportation companies, and the Energy Transportation Company, E.T.C. :::align{center}  ::: Bob, one of my friends, works in E.T.C. "E.T.C. has a good working environment, excellent dining, adequate compensation, and plenty of leisure time. If you work there, when you finish all your work and walk out of the gate at 3 p.m., you will definitely feel happy and comfortable," Bob says. Above is some introduction about E.T.C. But don't pay too much attention to the descriptions what are all fictional. The problem statement below is not related to E.T.C. or the text above. :::: > 为保证图片质量，请确认你的电脑已下载 Caviar Dreams 字体。

在某个世界里，有一个叫作**能量**的东西，存在于某些物质中。但和我们所在的世界不一样的是，有时能量会脱离物质单独出现。此时，我们通常用 $E$ 来表示能量的大小，其中 $E$ 是任意整数。 有时候，一些能量会汇聚到同个地方，此时这些能量会相互合并，形成更大的能量，新的能量的大小为其中所有能量大小的总和。 与此同时，有一个叫作能量输送公司的公司，这里我们简称它为 E.T.C.。E.T.C. 创立初期，业务仅有能量的转存和能量的运送。随着时代的发展和各种供应需求的增加，E.T.C. 逐渐成为一个~~物联网公司~~体系成熟的多功能公司。 E.T.C. 有一个新兴产业：使用能量进行运算。研究者们发明了一套机器，这些机器有的可以凭空产生一些能量，有的可以让能量加倍，而有的甚至可以将能量转化为对应大小的**负能量**！ > 大小为 $F$ 的负能量可以理解为大小为 $-F$ 的能量。换句话说，负能量在和能量合并时会以相同的比例互相消耗，直到其中一者消失。 几天前，E.T.C. 新购入了这套机器。 我们把所有需要用的机器摆放到新开设的计算厂间，将机器编号为 $1$ 到 $N$，并使用能量管道连接起来。其中有一些特殊的可以和工人进行输入输出交互的机器，方便人们操作。这个包含输入输出和运算处理的机器和能量管道的集合组成了能够处理一些较为固定操作的结构，我们称其为**程序**。 在一个程序里，每个机器会以相同频率运作，我们把这个频率叫作**回合**。每个回合，机器会根据其上一回合被输入的所有能量的总和，和机器本身的设置，向特定的一个／几个机器输出一定大小的能量。定义程序开始运行的时刻为回合 $0$，我们就可以对每个机器的某一时刻进行的操作进行描述。 记当前的回合数为 $t$，回合 $t$ 向输入编号为 $\textrm{id}$ 的输入机器的输入分别为 $I_{t,\textrm{id}}$，机器 $i$ 在回合 $t$ 收到的来自机器的总输出为 $E_{t,i}$，向机器 $\textrm{out}$ 输出 $X$ 大小的能量并使其在下回合被机器 $\textrm{out}$ 收到的操作为 $X \to \textrm{out}$。\ 初始回合 $E_{0,i}$ 均为 $0$。\ 那么，机器 $i$ 在回合 $t$ 的操作可以被分为以下几种： |名称|记号|操作数|计算方式| |:--:|:--:|:---|:---| |输入机器|`I`|`id out`|${I_{t,\textrm{id}} \to \textrm{out}}$| |输出机器|`O`|无|**一个程序里需要有恰好一个**。若 ${E_{t,i} \not= 0}$，则终止整个程序，并将 ${E_{t,i}}$ 作为程序的总输出。**保证答案不为 $\mathbf 0$。**| |产能机器|`P`|`amount out`|${\begin{cases} E_{t,i} + \textrm{amount} \to \textrm{out} & E_{t,i} \ge 0 \\ \min(E_{t,i} + \textrm{amount}, 0) \to \textrm{out} & E_{t,i} < 0 \end{cases}}$| |消能机器|`R`|`amount out`|${\begin{cases} \max(E_{t,i} - \textrm{amount}, 0) \to \textrm{out} & E_{t,i} \ge 0 \\ E_{t,i} - \textrm{amount} \to \textrm{out} & E_{t,i} < 0 \end{cases}}$| |取反机器|`N`|`out`|${-E_{t,i} \to \textrm{out}}$| |复制机器|`C`|`out1 out2`|${E_{t,i} \to \textrm{out}_1}$，${E_{t,i} \to \textrm{out}_2}$| |延时机器|`T`|`out`|有两种状态：闲置状态和工作状态。初始时为闲置状态。若它处于闲置状态且 ${E_{t,i} \not= 0}$，则它会变为工作状态；在第 ${t + \operatorname{abs}(E_{t,i})}$ 回合，它会从工作状态变回闲置状态，并执行：${\begin{cases}\sum_{j = t + 1}^{t + E_{t,i}}{E_{j,i}} \to \textrm{out} & E_{t,i} > 0 \\ E_{t-E_{t,i},i} \to \textrm{out} & E_{t,i} < 0 \end{cases}}$| |判断机器|`D`|`x1 out1 x2 out2 x3 out3`|${\begin{cases} x_1 \to \textrm{out}_1 & E_{t,i} < 0 \\ x_2 \to \textrm{out}_2 & E_{t,i} = 0 \\ x_3 \to \textrm{out}_3 & E_{t,i} > 0 \\ \end{cases}}$| 以上所有参数均需要满足 $1 \le \textrm{out}, \textrm{out}_1, \textrm{out}_2, \textrm{out}_3 \le N$，$0 \le \textrm{amount}, |x_1|, |x_2|, |x_3| \le 10^9$。 另外地，如果要求的输入机器共有 $M$ 个，那么所有 $\textrm{id}$ 均需要满足 $1 \le \textrm{id} \le M$ 且 $1 \sim M$ 中的所有数字各出现了恰好一次。 特别地，机器有其识别能力上限。如果机器 $i$ 在回合 $t$ 收到的总输出 $E_{t,i}$ 的绝对值大于 $10^9$，那么 $E_{t,i}$ 将被舍入到相同符号的绝对值为 $10^9$ 的数字。 经过一定的经验积累，我们发现在很多情况下，很难通过调整程序的结构来适应输入的速度。后来我们积极地和客户协商，加强了我们输入的自由度。现在我们可以设定一个正整数输入因子 $I_F$，表示输入被放慢的倍率。设初始的输入矩阵为 $U$，那么实际使用的输入矩阵 $I$ 满足 $I_{t \cdot I_F, i} = U_{t, i}$，且未指定的所有位置均为 $0$。 现在我们把程序设计的任务转交给了你。你需要解决下面的任务，使**机器的个数**和**产生输出的用时**小到一定级别： :::info[任务 1]{open} 在 $I_{0,1}$ 输入 $x$，输出 $114514$。$1 \le |x| \le 10^9$。 ::: :::info[任务 2]{open} 在 $I_{0,1}$ 输入 $x$，然后在 $I_{1,1}$ 输入 $y$，输出 $x + y$。$1 \le |x|,|y| \le 100$。 ::: :::info[任务 3]{open} 在 $I_{0,1}$ 和 $I_{0,2}$ 分别输入 $x,y$，输出 $x \times y$。$1 \le x,y \le 100$。 ::: :::info[任务 4]{open} 在 $I_{0,1}$ 和 $I_{0,2}$ 分别输入 $x,y$，输出 $\min(x,y)$。$1 \le x,y \le 100$。 ::: :::info[任务 5]{open} 在 $I_{0,1}$ 输入 $x$，输出序列 ${A = \{1, 1, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, 13\}}$ 的第 $x$ 项，也就是 $A_x$。$1 \le x \le |A|$。 ::: :::info[任务 6]{open} 对于 $0 \le i < 20$ 的每个整数 $i$，在 $I_{i,1}$ 输入 $a_i$，输出 $\sum_{0 \le i < 20}{2^{19-i}a_i}$。$a_i \in \{0,1\}$。 ::: :::info[任务 7]{open} 在 $I_{0,1}$ 输入 $n$，$I_{0,2}$ 输入 $k$，然后对于 $1 \le i \le n$ 的所有整数 $i$，在 $I_{i,3}$ 输入 $a_i$，输出 $\sum_{k \mid i}a_i$。$1 \le k \le n \le 100$，$1 \le a_i \le 100$。 ::: :::info[任务 8]{open} 在 $I_{0,1}$ 输入 $n$，然后对于 $1 \le i \le n$ 的所有整数 $i$，在 $I_{i,2}$ 输入 $a_i$，输出 $\max(a_1,a_2,\dots,a_n)$。$1 \le n, a_i \le 100$。 ::: :::info[任务 9]{open} 在 $I_{0,1}$ 输入 $n$，$I_{0,2}$ 输入 $k$，然后对于 $1 \le i \le n$ 的所有整数 $i$，在 $I_{i,3}$ 输入 $a_i$，输出最小的满足 $a_i = k$ 的下标 $i$。保证存在恰好一个 $a_i = k$。$1 \le n \le 100$，$1 \le k, a_i \le 100$。 :::

输入仅包含一行一个整数，表示需要解决的任务的编号。特别的，在样例中，编号为 $0$。

第一行输出两个正整数，分别为你使用的机器个数 $N$ 和你指定的输入因子 $I_F$。 后面 $N$ 行，第 $i$ 行用于描述机器 $i$。 描述每个机器时，先输出一个大写字母表示该计算节点的类型，接下来若干个非负整数按上表顺序表示该机器的参数。大写字母和数，数和数之间均用空格隔开。

样例输出为一个在回合 $1$ 输出 $I_{0,1}$ 的程序。 --- 我们在下发文件 `wisdom.zip` 提供了九个评分文件 `wisdom1.ans`～`wisdom9.ans`，分别对应每个任务。 每个评分文件共 $6$ 行，第 $i + 1$ 行有两个评分参数 $n_i$ 和 $t_i$，具体意义将在下面给出。 本题中，每个测试点单独进行评分，每个测试点 $40$ 分。 如果选手输出的 $N$ 大于 $n_5$、输出格式不合法或者参数不符合题目约定，则得 $0$ 分。 否则，按照以下规则判定选手的输出是否正确： - 首先测评器会生成若干组输入数据，并将输入数据按照格式放入矩阵 $I$，然后运行程序； - 如果你的程序运行了 $t_5$ 回合仍未输出答案，或者输出和预期的输出不相同，得 $0$ 分； - 否则，我们认为你的程序完成了这一项任务。 对于每个测试点，我们设置了 $12$ 个评分参数：$n_0,n_1,n_2,n_3,n_4,n_5$ 和 $t_0,t_1,t_2,t_3,t_4,t_5$。 你的程序可以完成对应任务时，设你的程序有 $N$ 个机器，并在测试数据下**最晚**在第 $T$ 回合输出，那么我们找到最小的 ${i,j}$ 满足 ${N \le n_i}$ 且 ${T \le t_j}$，则你的程序在这个测试点获得 ${4 \times \min\left(10, 12 - i - j\right)}$ 分。 注意，由于两个评分参数的同时作用，所以为了获取到更多分数，你必须对你的程序的**效率**和**大小**做出一定的取舍。 `wisdom.zip` 中有模拟器 `simulator.cpp`。Special Judge 实现和这份文件基本相同。使用方式可以直接查看代码得到，这里不再赘述。