CF26E.Multithreading

You are given the following concurrent program. There are N processes and the i-th process has the following pseudocode:

repeat n__i times
y__i := y
y := y__i + 1
end repeat

Here y is a shared variable. Everything else is local for the process. All actions on a given row are atomic, i.e. when the process starts executing a row it is never interrupted. Beyond that all interleavings are possible, i.e. every process that has yet work to do can be granted the rights to execute its next row. In the beginning y = 0. You will be given an integer W and n__i, for i = 1, ... , N. Determine if it is possible that after all processes terminate, y = W, and if it is possible output an arbitrary schedule that will produce this final value.

你将得到以下并发程序。共有 $N$ 个进程，其中第 $i$ 个进程具有如下伪代码：

重复 $n_i$ 次
 $y_i := y$
 $y := y_i + 1$
结束重复

其中 $y$ 是一个共享变量，其余所有变量均为各进程的局部变量。每一行上的所有操作都是原子的，即：当某个进程开始执行某一行时，该执行过程绝不会被中断。除此之外，所有可能的交错执行（interleaving）均被允许，即：任意一个尚未完成全部工作的进程，都可能被授予执行其下一行的权限。初始时 $y = 0$。你将被给定一个整数 $W$ 以及 $n_i$（其中 $i = 1, \dots, N$）。请判断：在所有进程终止后，是否可能使 $y = W$；若可能，请输出任意一个能达成该最终值的调度方案。

In the first line of the input you will be given two space separated integers N (1 ≤ N ≤ 100) and W ( - 109 ≤ W ≤ 109). In the second line there are N space separated integers n__i (1 ≤ n__i ≤ 1000).

输入的第一行包含两个以空格分隔的整数 $N$（$1 ≤ N ≤ 100$）和 $W$（$-10^9 ≤ W ≤ 10^9$）。第二行包含 $N$ 个以空格分隔的整数 $n_i$（$1 ≤ n_i ≤ 1000$）。

On the first line of the output write Yes if it is possible that at the end y = W, or No otherwise. If the answer is No then there is no second line, but if the answer is Yes, then on the second line output a space separated list of integers representing some schedule that leads to the desired result. For more information see note.

在输出的第一行，如果最终可能使 $y = W$，则输出 Yes；否则输出 No。若答案为 No，则不输出第二行；若答案为 Yes，则在第二行输出一个由空格分隔的整数列表，表示一种可达成目标结果的调度方案。更多说明请参见注释。

For simplicity, assume that there is no repeat statement in the code of the processes, but the code from the loop is written the correct amount of times. The processes are numbered starting from 1. The list of integers represent which process works on its next instruction at a given step. For example, consider the schedule 1 2 2 1 3. First process 1 executes its first instruction, then process 2 executes its first two instructions, after that process 1 executes its second instruction, and finally process 3 executes its first instruction. The list must consists of exactly 2·Σ i = 1...N n__i numbers.

为简化问题，假设进程的代码中不包含循环语句，但若原代码中存在循环，则已将循环体展开为正确次数。进程编号从 1 开始。整数列表表示在每个时间步中执行其下一个指令的进程编号。例如，考虑调度序列 1 2 2 1 3：首先进程 1 执行其第一条指令；接着进程 2 连续执行其前两条指令；然后进程 1 执行其第二条指令；最后进程 3 执行其第一条指令。该列表必须恰好包含 $2 \cdot \sum_{i=1}^{N} n_i$ 个数字。