P15874 [NOI1998] 并行计算

NOI1998 D2T3

运算器（ALU）是计算机中的重要部件，它的功能是进行数学运算。图一是运算器的工作简图，运算器的一次运算操作过程为：运算器在控制器的控制下，从指定的存储器（MEMORY）存储单元中读出待运算的两个源操作数 $A$ 和 $B$，经过一定时间的计算后得到运算结果 $C$，并将它写入指定的存储器存储单元中。 :::align{center}  图一 ::: 运算器能完成的运算种类及所需时间如下表所示： | 运算种类 | 运算操作 | 所需运算时间 | | :----------: | :----------: | :----------: | | $1$ | $C=A+B$ | $T_\text{add}$ | | $2$ | $C=A-B$ | $T_\text{sub}$ | | $3$ | $C=A\times B$ | $T_\text{mul}$ | | $4$ | $C=A\div B$ | $T_\text{div}$ | 在计算复杂的四则混合运算表达式时，运算器就变成了高速计算的“瓶颈”。为了得到更快的运算速度，计算机科学家们设计了一种有两个运算器的并行计算机，它的结构简图如图二所示。 :::align{center}  图二 ::: 由于两个运算器可以同时进行运算，因此大大提高了整机运算速度。 该并行计算机有以下两种控制指令： - 运算指令：`OP Time Alu_no Operate_no Address1 Address2 Address3`。 其中 `OP` 为运算指令标识符，其后有六个参数： - `Time` 表示执行该指令的开始时间。 - `Alu_no` 表示承担该次运算操作的运算器编号（$\text{Alu\_no}\in\{1,2\}$）。 - `Operate_no` 表示该次运算的运算种类（$\text{Operate\_no}\in\{1,2,3,4\}$）。 - `Address1`、`Address2` 表示待运算的两个源操作数的存储单元地址。 - `Address3` 表示该次运算结束后存放运算结果的存储单元地址。 - 结束指令：`END Time Address`。 其中 `END` 为结束指令标识符，其后有两个参数： - `Time` 表示整个控制程序的结束时间。 - `Address` 表示存放最终计算结果的存储单元地址。 每个运算器同一时刻可以执行一条运算指令，结束指令表示控制程序结束。 现在需要你编一个程序，对给定的待计算的表达式，自动生成一段控制程序，使图二所示的并行计算机能够正确计算该表达式的值，并使总运算时间尽量小。

输入文件的第一行为四个不超过 $1000$ 的正整数，依次为 $T_\text{add}$、$T_\text{sub}$、$T_\text{mul}$ 和 $T_\text{div}$。 输入文件的第二行为待计算的四则混合运算表达式（长度不超过 $255$ 个字符），表达式中的变量用大写英文字母表示，各变量的初始值依照变量的字母顺序依次存放在地址为 $1,2,\dots$ 的存储单元中。 输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出文件为完成该表达式计算的最优控制指令段。指令根据其开始执行时间先后依次输出（对于开始执行时间相同的两条指令，输出先后次序不限），每条指令占一行。 输出文件中同一行相邻两项之间用一个空格隔开。

**【数据说明】** - Subtask 0 为 CCF 官方数据，强度较低。 - Subtask 1 为民间数据。 **【约定】** - 控制程序初始执行时间从 $0$ 时刻开始。 - 问题中所涉及的各种时间量的单位相同。 存储器的存储单元最多有 $1000$ 个。 - 由于数据读写时间同运算时间相比较小，可忽略不计。 - 如果两个运算器同时对同一个存储单元进行操作，则运算器 $1$ 先操作，运算器 $2$ 后操作。 **【评分】** 程序的得分将取决于其所能找到的最优解与标准最优解相比较的优劣程度。 **注意**：由于原题并未说明得分规则，且得分方式较模糊。因本题为启发式问题，各测试点得分规则如下： - 可以证明，本题中理论上可能达到的最大最优总运算时间为 $85000$，所以： - 如果答案不正确，测试点得 0 分； - 否则，测试点得分为 $85000 - \text{Time}$。 本题 AC 需总得分**不少于** $1415000$。