[NOI1998]并行计算

成绩 0 开启时间 2013年01月22日 星期二 13:50
折扣 0.8 折扣时间 2013年01月22日 星期二 13:50
允许迟交 关闭时间 2013年01月22日 星期二 13:50
输入文件 parallel.in 输出文件 parallel.out

运算器(ALU)是计算机中的重要部件,它的功能是进行数学运算。图一是运算器的工作简图,运算器的一次运算操作过程为:运算器在控制器的控制下, 从指定的存储器(MEMORY)存储单元中读出待运算的两个源操作数A和B,经过一定时间的计算后得到运算结果C,并将它写入指定的存储器存储单元中。

Image:Parallel1.jpg 图一

运算器能完成的运算种类及所需时间如下表所示:

运算种类 运算操作 所需运算时间
1 C=A+B Tadd
2 C=A-B Tsub
3 C=A*B Tmul
4 C=A/B Tdiv

在计算复杂的四则混合运算表达式时,运算器就变成了高速计算的“瓶颈”。为了得到更快的运算速度,计算机科学家们设计了一种有两个运算器的并行计算机,它的结构简图如图二所示。

Image:Parallel2.jpg 图二

由于两个运算器可以同时进行运算,因此大大提高了整机运算速度。该并行计算机有以下两种控制指令:

运算指令

  • OP Time Alu_no Operate_no Address1 Address2 Address3

其中OP为运算指令标识符,其后有六个参数:

  • Time表示执行该指令的开始时间
  • Alu_no表示承担该次运算操作的运算器编号(Alu_no∈{1,2})
  • Operate_no表示该次运算的运算种类(Operate_no∈{1,2,3,4})
  • Address1,Address2表示待运算的两个源操作数的存储单元地址
  • Address3表示该次运算结束后存放运算结果的存储单元地址

结束指令

  • END Time Address

其中 END为结束指令标识符,其后有两个参数:

  • Time表示整个控制程序的结束时间
  • Address表示存放最终计算结果的存储单元地址

每个运算器同一时刻可以执行一条运算指令,结束指令表示控制程序结束。

现在需要你编一个程序,对给定的待计算的表达式,自动生成一段控制程序,使图二所示的并行计算机能够正确计算该表达式的值,并使总运算时间尽量小。

输入

输入文件的第一行为四个不超过1000的正整数,依次为Tadd、Tsub、Tmul和Tdiv。 输入文件的第二行为待计算的四则混合运算表达式(长度不超过255个字符),表达式中的变量用大写英文字母表示,各变量的初始值依照变量的字母顺序依次存 放在地址为1,2,…的存储单元中。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出

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

约定

  • 控制程序初始执行时间从0时刻开始。
  • 问题中所涉及的各种时间量的单位相同。
  • 存储器的存储单元最多有1K个。
  • 由于数据读写时间同运算时间相比较小,可忽略不计。
  • 如果两个运算器同时对同一个存储单元进行操作,则运算器1先操作,运算器2后操作

评分

  • 程序的得分将取决于其所能找到的最优解与标准最优解相比较的优劣程度。

样例输入

2 2 4 12
C+(A+B)*C-E/F+F

样例输出

OP 0 1 1 1 2 6
OP 0 2 4 4 5 8
OP 2 1 1 3 5 7
OP 4 1 3 6 3 10
OP 8 1 1 10 7 11
OP 12 1 2 11 8 12
END 14 12