P9429 [NAPC-#1] Stage1 - Simple

> 

### 【简要题意】 给定 $n,m,k,S$，请构造长度为 $n$ 的整数序列 $a$ 使得： - $0\leqslant a_i\leqslant m,\forall i\in[1,n]$（即序列 $a$ 内的每个元素均不小于 $0$ 且不大于 $m$）。 - $|a_i-a_{i-1}|\leqslant k,\forall i\in(1,n]$（即序列 $a$ 内的每两个相邻元素之差的绝对值均不大于 $k$）。 - $(\sum_{i=1}^n a_i ) = S$（即序列 $a$ 内的所有元素的和为 $S$）。 **保证有解。** ### 【原始题意】 前面忘了，但是~~你随 kid 穿越到了 ic~~（I wanna be the Creator），来到了一个关卡编辑器面前。该地图宽为 $n$，高为 $(m+1)$，是你不能修改的；里面还有 $S$ 个 $1\times1$ 大小的未摆放的砖。现在你需要帮 kid 摆好这一面，也就是说，将这 $S$ 个砖摆放好，使得他可以通过。有以下要求： 1. ~~砖是有重力的~~，所以**一块砖只能摆放在下边界上或者另一块砖上**。同一横纵坐标不能摆放多块砖。 2. 你至少要给 kid 留一条缝来通过，所以每一列你最高只能放 $m$ 块砖（地图高度为 $m+1$）。但是注意，ic 关卡下边界没有伤害，某一列是可以不放砖块的。 3. kid 的跳跃能力和~~从高处坠落而不受伤的能力~~是有限的，这用一个非负整数 $k$ 来描述：相邻两列摆放的砖的数量之差的绝对值不能超过 $k$，否则该关卡对 kid 来说就是无解的。_（但是注意：该条对第一列高度没有要求，kid 出生点就在第一列。）_ 4. 你要把所有 $S$ 块砖都摆进去，不多不少。 Creator 不会为难你，因此一定有一种关卡符合上述所有规则。 为了输出方便，你只需要给出第 $i$ 列有多少砖块（记为 $a_i$），输出 $a$ 序列即可。容易证明，一个合法的 $a$ 序列和一个合法关卡是一一对应的。

仅一行 $4$ 个非负整数 $n,m,k,S$。

输出一行 $n$ 个非负整数表示你构造的序列 $a$。如果有多种可能的序列，输出任意一个符合题意的序列即可。**保证至少有一个序列满足题目要求。**

### 【数据范围】 该题共有 $10$ 个测试点，每个测试点等分。 - 对于 $20\%$ 的数据，$S=n\cdot m$。 - 对于 $20\%$ 的数据，$k=0$。 - 对于 $20\%$ 的数据，$k=10^9$。 对于 $100\%$ 的数据，$1\leqslant n,m\leqslant 10^5$，$0\leqslant k\leqslant 10^9$，$0\leqslant S\leqslant n\cdot m$。 ### 【提示】 > 古之有数，其名为 $S$。$S$ 之大，一个 `int` （可能）装不下。 ### 【样例解释 #1】 样例输出对应关卡如下。  注意可能有多种合法关卡均符合条件。