题目描述
给定如下并发程序:有N个进程,第i个进程的伪代码如下:
重复nᵢ次
yᵢ := y
y := yᵢ + 1
结束重复
其中y是一个共享变量,其他所有变量都是进程本地的。每一行的操作都是原子性的,即进程开始执行某一行时不会被中断。除此之外,所有的执行交错都是允许的,即任何还有任务未完成的进程都可以被授予执行下一行的权限。初始时y=0。给定整数W和nᵢ(i=1,…,N),请判断是否存在一种执行顺序,使得所有进程终止后y=W。如果存在,输出任意一种可以产生该结果的执行调度。
输入格式
第一行输入两个空格分隔的整数N(1≤N≤100)和W(-10⁹≤W≤10⁹)。 第二行输入N个空格分隔的整数nᵢ(1≤nᵢ≤1000)。
输出格式
第一行输出"Yes"如果最终y=W是可能的,否则输出"No"。如果答案是"No",则无需输出第二行;如果答案是"Yes",第二行输出一个由空格分隔的整数列表,表示可以得到期望结果的执行调度。
输入输出样例
输入#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
说明/提示
为简化理解,可以认为进程代码中没有repeat语句,而是将循环内的代码重复了指定的次数。进程编号从1开始。整数列表表示每个步骤中哪个进程执行其下一条指令。例如,考虑调度序列1 2 2 1 3:首先进程1执行其第一条指令,然后进程2执行其前两条指令,接着进程1执行其第二条指令,最后进程3执行其第一条指令。列表必须恰好包含2·Σnᵢ个数字。