为您提供以下并发程序。有 N 个进程,第 i 个进程的伪代码如下:
这里 y 是一个共享变量。对于该过程来说,其他一切都是本地的。给定行上的所有操作都是原子的,即当进程开始执行一行时,它永远不会被中断。除此之外,所有交错都是可能的,即每个尚未完成工作的进程都可以被授予执行其下一行的权利。一开始 y = 0。您将得到一个整数 W 和 ni,其中 i = 1,...,N。确定是否有可能在所有进程终止后,y = W,如果可能,则输出将产生此最终值的任意时间表。
输入
在输入的第一行中,您将得到两个空格分隔的整数 N (1 ≤ N ≤ 100) 和 W (- 109 ≤ W ≤ 109)。第二行有 N 个空格分隔的整数 ni (1 ≤ ni ≤ 1000)。
输出
如果最后 y = W 可能,则在输出的第一行写入 Yes,否则写入 No。如果答案为“否”,则没有第二行,但如果答案为“是”,则在第二行输出一个空格分隔的整数列表,表示导致所需结果的某个时间表。有关详细信息,请参阅注释。
示例
输入 #1
1 10 11
输出 #1
No
输入 #2
2 3 4 4
输出 #2
Yes 1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 2
输入 #3
3 6 1 2 3
输出 #3
Yes 1 1 2 2 2 2 3 3 3 3 3 3
注意
为简单起见,假设进程代码中没有重复语句,但循环中的代码被写入了正确的次数。进程从 1 开始编号。整数列表表示哪个进程在给定步骤中处理其下一条指令。例如,考虑调度 1 2 2 1 3。首先进程 1 执行其第一条指令,然后进程 2 执行其前两条指令,之后进程 1 执行其第二条指令,最后进程 3 执行其第一条指令。该列表必须恰好包含 2·Σ i = 1...N ni 个数字。