有一条宽度为 $$$n$$$ 的河流。河流的左岸是单元格 $$$0$$$,右岸是单元格 $$$n + 1$$$(更正式地说,河流可以表示为 $$$n + 2$$$ 单元格的序列,编号从 $$$0$$$ 到 $$$n + 1$$$)。河流上还有 $$$m$$$ 个木平台,第 $$$i$$$ 个平台的长度为 $$$c_i$$$ (因此第 $$$i$$$ 个平台占用河流的 $$$c_i$$$ 连续单元格)。 It is guaranteed that the sum of lengths of platforms does not exceed $$$n$$$.
You are standing at $$$0$$$ and want to reach $$$n+1$$$ somehow. If you are standing at the position $$$x$$$, you can jump to any position in the range $$$[x + 1; x + d]$$$。 However you don't really like the water so you can jump only to such cells that belong to some wooden platform. For example, if $$$d=1$$$, you can jump only to the next position (if it belongs to the wooden platform). You can assume that cells $$$0$$$ and $$$n+1$$$ belong to wooden platforms.
您想知道如果您可以将任何平台向左或向右移动任意次数(可能是零),只要它们不相交(但两个平台可以互相接触),是否可以从 $$$0$$$ 到达 $$$n+1$$$。这也意味着您无法更改平台的相对顺序。
请注意,您应该移动平台直到开始跳跃(换句话说,您首先移动平台然后开始跳跃)。
例如,如果 $$$n=7$$$、$$$m=3$$$、$$$d=2$$$ 且 $$$c = [1, 2, 1]$$$,则从 $$$0$$$ 到达 $$$8$$$ 的方法之一如下:
第一个例子:$$$n=7$$$。
输入
输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$d$$$ ($$$1 \le n, m, d \le 1000, m \le n$$$) — 分别是河流的宽度、平台的数量和跳跃的最大距离。
输入的第二行包含 $$$m$$$ 整数 $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le n, \sum\limits_{i=1}^{m} c_i \le n$$$),其中 $$$c_i$$$ 是第 $$$i$$$ 个平台的长度。
输出
如果从$$$0$$$不可能到达$$$n+1$$$,则在第一行打印NO。否则,在第一行中打印 YES,并在第二行中打印长度为 $$$n$$$ 的数组 $$$a$$$ — 河流单元的序列(不包括单元 $$$0$$$ 和单元 $$$n + 1$$$)。
如果单元格 $$$i$$$ 不属于任何平台,则 $$$a_i$$$ 应为 $$$0$$$。否则,它应该等于单元格$$$i$$$所属的平台索引($$$1$$$索引,平台按输入顺序从$$$1$$$编号到$$$m$$$)。
请注意,所有等于$$$1$$$的$$$a_i$$$应形成长度为$$$c_1$$$的数组$$$a$$$的连续子段,等于$$$2$$$的所有$$$a_i$$$应形成长度为$$$c_2$$$的数组$$$a$$$的连续子段, ...,所有等于 $$$m$$$ 的 $$$a_i$$$ 应该形成长度为 $$$c_m$$$ 的数组 $$$a$$$ 的连续子段。 $$$a$$$中$$$2$$$的最左位置应大于$$$1$$$的最右位置,$$$a$$$中$$$3$$$的最左位置应大于$$$2$$$的最右位置,...,$$$a$$$中$$$m$$$的最左位置应大于$$$m-1$$$的最右位置。
请参阅示例输出以更好地理解。
示例
输入 #1
7 3 2 1 2 1
输出 #1
YES 0 1 0 2 2 0 3
输入 #2
10 1 11 1
输出 #2
YES 0 0 0 0 0 0 0 0 0 1
输入 #3
10 1 5 2
输出 #3
YES 0 0 0 0 1 1 0 0 0 0
注意
考虑第一个示例:答案是 $$$[0, 1, 0, 2, 2, 0, 3]$$$。您执行的跳跃顺序为 $$$0 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 7 \rightarrow 8$$$。
考虑第二个例子:如何放置平台并不重要,因为你总是可以从 $$$0$$$ 跳到 $$$11$$$。
考虑第三个例子:答案是$$$[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]$$$。您执行的跳跃顺序为 $$$0 \rightarrow 5 \rightarrow 6 \rightarrow 11$$$。