← 返回题目列表

Codeforces · 26/E

E. 多线程

中文机器翻译题面 查看原题

为您提供以下并发程序。有 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 个数字。