编程介的小学生 2017-11-04 13:25 采纳率: 20.5%
浏览 777
已采纳

Assembling Services

Problem Description
In this problem, you need to simulate the execution of n service programs P1, P2, ..., Pn. Each program is described with sequence of integers: T I in1 in2 ... inI O out1 out2 ... outO, that means it takes T unit time to execute, needs I input variables (i.e. in1 in2 ... inI), and sets O output variables (i.e. out1 out2 ... outO) when it finishes running. A program can be started if and only if all these T input variables are ready (initially available, or set by some other programs).

Imagine you have a super-computer which can execute as many programs in parallel as you like, and every variable can be read and written simultaneously by multiple programs. Your task is to calculate a particular "target" variable, as soon as possible.

Assume there are 4 programs, shown in the table below:

The quickest time to get X5 is 7, if only X1 is available at startup.

You also need to construct an expression that shows how to execute the programs to achieve the minimal time. The grammar of the expression is recursive:
Single Program: Px, where 1 <= x <= n. (i.e. P2, P499, etc). Meaning: execute the program immediately. Then end of this program marks the end of this expression.

Execute in serial: (S1S2...Sk), where every Si is an expression. Note that the outermost pair of parentheses is mandatory. Meaning: execute expression S1, then S2 immediately after S1 ends, then S3 immediately after S2 ends, ..., and finally Sk immediately after Sk-1 ends. Then end of expression Sk marks the end of the whole expression.

Execute in parallel: (S1|S2|...|Sk), where every Si is an expression. Note that the outermost pair of parentheses is mandatory. Meaning: execute expressions S1, S2, ..., and Sk simultaneously. The end of last finished expression marks the end of the whole expression.
One of the possible expressions for the example above is (((P1P3)|P2)P4). (P1P2P3P4)is not acceptable, since X5 is available at time 10 in that expression, later than the optimal time 7.

Input
There will be at most 100 test cases. Each case begins with three integers n, m, o(1 <= n,m <= 500, 1 <= o <= m). The number of programs is n, the number of variables is m, and the target variable is Xo. Variables are numbered 1 to m, programs are numbered 1 to n. The next line contains a 01 string of m characters. The i-th character is 1 if and only if the i-th variable is initially available. The target variable is guaranteed to be unavailable at startup. The following n lines describe the programs. Each line begins with an integer T(1 <= T <= 100), the execution time, and an integer I followed by I integers in1, in2, ..., inI, as stated above, then an integer O followed by O integers out1, out2, ..., outO. 1 <= ini,outi <= m, 1 <= I,O <= 10. The last test case is followed by n=m=o=0, which should not be processed.

Output
For each test case, print the case number and the total time needed to get the target variable. If it's not possible to get the target variable, print -1 in stead.

If it's possible to get the target variable, print the expression after that, in the same line. Be sure to print a valid expression having at most 10,000 characters, with each program printed at most once. There should be no whitespace characters within the expression.

To make this problem a little bit easier, it's allowed that some programs finish after the optimal time, as long as the target variable is available at the optimal time. You’re also allowed to print redundant parentheses (pay attention to the expression length, though). If such an expression does not exist, print "Can't do in serial-parallel.", without quotes.

Print a blank line after the output of each test case.

Sample Input
4 5 5
10000
2 1 1 1 2
3 1 1 1 3
4 1 2 1 4
1 2 3 4 1 5
1 2 1
01
31 1 2 1 1
3 5 5
10100
3 1 1 1 2
1 1 3 1 4
3 2 4 2 1 5
1 3 3
100
1 1 1 1 2
0 0 0

Sample Output
Case 1: 7 (((P1P3)|P2)P4)

Case 2: 31 P1

Case 3: 6 ((P1P3)|P2)

Case 4: -1

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-11-29 15:47
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB yalmip 可转移负荷的简单建模出错,如何解决?
  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?