CF26E Multithreading

题目描述

给定以下并发程序:共有 $N$ 个进程,其中第 $i$ 个进程的伪代码如下: 循环执行 $n_i$ 次: $$ \begin{aligned} y_i &:= y\\ y &:= y_i + 1 \end{aligned} $$ 其中 $y$ 为共享变量,其余均为进程本地变量。每行操作都是不可分割的,即进程开始执行某行时不会被中断。除此之外所有交错执行顺序都可能发生,即每个有待执行任务的进程都可能获得执行下一行代码的权利。初始时 $y = 0$。给定整数 $W$ 和 $n_i$,判断所有进程终止后是否可能出现 $y = W$ 的情况。若可能,请输出任意一个能得到该最终值的执行调度方案。

输入格式

第一行输入两个空格分隔的整数 $N$($1 \leq N \leq 100$)和 $W$($ - 10^9 \leq  W \leq 10^9$)。第二行包含 $N$ 个空格分隔的整数 $n_i$($1 \leq  n_i \leq 1000$)。

输出格式

第一行输出 `Yes` 表示最终可能得到 $y = W$,否则输出 `No`。若答案为 `No` 则不需要第二行;若为 `Yes`,则在第二行输出一个空格分隔的整数列表表示能达到目标的调度方案。详见说明。

说明/提示

**【说明】** 为简化问题,假设进程代码中没有循环语句,而是将循环体代码按次数展开。进程编号从 `1` 开始。输出的整数列表表示每个步骤中执行下一条指令的进程编号。例如调度方案 `1 2 2 1 3`表示:进程 $1$ 执行第一条指令 $\to$ 进程 $2$ 连续执行前两条指令 $\to$ 进程 $1$ 执行第二条指令 $\to$ 进程 $3$ 执行第一条指令。该列表必须恰好包含 $2\times \sum\limits_{i=1}^N n_i$个数字。