P15874 [NOI1998] Parallel Computing

NOI1998 D2T3.

The Arithmetic Logic Unit (ALU) is an important component in a computer. Its function is to perform mathematical operations. Figure 1 shows a simplified workflow of an ALU. One operation proceeds as follows: under the control of the controller, the ALU reads two source operands $A$ and $B$ from the specified memory (MEMORY) cells, computes for a certain amount of time to obtain the result $C$, and then writes it into the specified memory cell. :::align{center}  Figure 1. ::: The types of operations the ALU can perform and the required time are shown in the table below: | Operation Type | Operation | Required Time | | :----------: | :----------: | :----------: | | $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}$ | When computing complex expressions involving mixed basic arithmetic operations, the ALU becomes a high-speed computing “bottleneck”. To obtain faster computing speed, computer scientists designed a parallel computer with two ALUs, whose structure is shown in Figure 2. :::align{center}  Figure 2. ::: Since the two ALUs can perform operations simultaneously, the overall computing speed is greatly improved. This parallel computer has the following two types of control instructions: - Operation instruction: `OP Time Alu_no Operate_no Address1 Address2 Address3`. Here `OP` is the operation instruction identifier, followed by six parameters: - `Time` indicates the start time of executing this instruction. - `Alu_no` indicates the ALU number that performs this operation ($\text{Alu\_no}\in\{1,2\}$). - `Operate_no` indicates the operation type ($\text{Operate\_no}\in\{1,2,3,4\}$). - `Address1` and `Address2` are the memory cell addresses of the two source operands. - `Address3` is the memory cell address where the result is stored after the operation ends. - Termination instruction: `END Time Address`. Here `END` is the termination instruction identifier, followed by two parameters: - `Time` indicates the end time of the entire control program. - `Address` indicates the memory cell address where the final result is stored. Each ALU can execute at most one operation instruction at the same time. The termination instruction indicates that the control program ends. Now you need to write a program that, for a given expression to be computed, automatically generates a control program so that the parallel computer shown in Figure 2 can correctly compute the value of the expression, and the total computation time is as small as possible.

The first line of the input file contains four positive integers not exceeding $1000$, in order: $T_\text{add}$, $T_\text{sub}$, $T_\text{mul}$, and $T_\text{div}$. The second line of the input file contains the mixed arithmetic expression to be computed (with length not exceeding $255$ characters). Variables in the expression are represented by uppercase English letters. The initial values of the variables are stored in memory cells with addresses $1,2,\dots$ in alphabetical order of the variable letters. In the input file, adjacent items on the same line are separated by one or more spaces.

Output the optimal sequence of control instructions that completes the computation of the expression. Instructions should be output in increasing order of their start time (for two instructions with the same start time, the output order does not matter). Each instruction occupies one line. In the output file, adjacent items on the same line are separated by one space.

**[Testdata Description]** - Subtask 0 uses the official CCF testdata, with relatively low difficulty. - Subtask 1 uses community-provided testdata. **[Conventions]** - The control program starts execution from time $0$. - All time quantities involved in the problem use the same unit. - The memory has at most $1000$ cells. - Since the time for data read/write is small compared with computation time, it can be ignored. - If two ALUs operate on the same memory cell at the same time, ALU $1$ operates first, and ALU $2$ operates afterward. **[Scoring]** The program score depends on how close the best solution it finds is to the standard optimal solution. **Note**: Since the original problem does not specify the scoring rules, and the scoring method is somewhat vague, this problem is a heuristic problem. The scoring rules for each test point are as follows: - It can be proven that the maximum theoretically possible optimal total computation time in this problem is $85000$, so: - If the answer is incorrect, the test point score is 0; - Otherwise, the test point score is $85000 - \text{Time}$. To get AC for this problem, the total score must be **no less than** $1415000$. Translated by ChatGPT 5