P9429 [NAPC-#1] Stage1 - Simple

> 

### Brief Statement Given $n, m, k, S$, construct an integer sequence $a$ of length $n$ such that: - $0 \leqslant a_i \leqslant m, \forall i \in [1, n]$ (each element of $a$ is at least $0$ and at most $m$). - $|a_i - a_{i-1}| \leqslant k, \forall i \in (1, n]$ (for every two adjacent elements in $a$, the absolute difference is at most $k$). - $(\sum_{i=1}^n a_i) = S$ (the sum of all elements in $a$ is $S$). **A solution is guaranteed to exist.** ### Original Statement I forgot what happened before, but ~~you followed kid and traveled to ic~~ (I wanna be the Creator) and arrived in front of a level editor. The map has width $n$ and height $(m+1)$, and you cannot change these. There are also $S$ unplaced $1 \times 1$ bricks. Now you need to help kid place them, meaning: place these $S$ bricks so that kid can pass. The requirements are: 1. ~~Bricks have gravity~~, so **a brick can only be placed on the bottom boundary or on top of another brick**. You cannot place multiple bricks at the same $(x, y)$ coordinate. 2. You must leave at least one gap for kid to pass, so in each column you can place at most $m$ bricks (since the map height is $m+1$). Note that in ic levels, the bottom boundary does not cause damage, so a column may also have no bricks. 3. kid’s jumping ability and ~~the ability to fall from a height without getting hurt~~ are limited, described by a non-negative integer $k$: the absolute difference between the numbers of bricks placed in adjacent columns cannot exceed $k$, otherwise the level is impossible for kid. _((But note: this rule does not restrict the height of the first column, since kid’s spawn point is in the first column.))_ 4. You must place all $S$ bricks, no more and no less. Creator will not make things difficult for you, so there is always a level that satisfies all the rules above. For easier output, you only need to give how many bricks are in the $i$-th column (denote it as $a_i$), i.e., output the sequence $a$. It is easy to prove that a valid sequence $a$ corresponds one-to-one with a valid level.

A single line with $4$ non-negative integers $n, m, k, S$.

Output one line with $n$ non-negative integers representing your constructed sequence $a$. If there are multiple possible sequences, output any one that satisfies the requirements. **It is guaranteed that at least one sequence satisfies the requirements.**

### Constraints This problem has $10$ test points, equally weighted. - For $20\%$ of the testdata, $S = n \cdot m$. - For $20\%$ of the testdata, $k = 0$. - For $20\%$ of the testdata, $k = 10^9$. For $100\%$ of the testdata, $1 \leqslant n, m \leqslant 10^5$, $0 \leqslant k \leqslant 10^9$, $0 \leqslant S \leqslant n \cdot m$. ### Hint > In ancient times there was a number, its name was $S$. $S$ can be so large that one `int` may (possibly) not hold it. ### Sample Explanation #1 The level corresponding to the sample output is as follows.  Note that there may be multiple valid levels that meet the conditions. Translated by ChatGPT 5