{"problem":{"name":"[NAPC-#1] Stage1 - Simple","description":{"content":"### 【简要题意】 给定 $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$ 内的每两个相邻元素之差的绝对","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P1"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9429"},"statements":[{"statement_type":"Markdown","content":"### 【简要题意】\n给定 $n,m,k,S$，请构造长度为 $n$ 的整数序列 $a$ 使得：\n- $0\\leqslant a_i\\leqslant m,\\forall i\\in[1,n]$（即序列 $a$ 内的每个元素均不小于 $0$ 且不大于 $m$）。\n- $|a_i-a_{i-1}|\\leqslant k,\\forall i\\in(1,n]$（即序列 $a$ 内的每两个相邻元素之差的绝对值均不大于 $k$）。\n- $(\\sum_{i=1}^n a_i ) = S$（即序列 $a$ 内的所有元素的和为 $S$）。\n\n**保证有解。**\n\n### 【原始题意】\n\n前面忘了，但是~~你随 kid 穿越到了 ic~~（I wanna be the Creator），来到了一个关卡编辑器面前。该地图宽为 $n$，高为 $(m+1)$，是你不能修改的；里面还有 $S$ 个 $1\\times1$ 大小的未摆放的砖。现在你需要帮 kid 摆好这一面，也就是说，将这 $S$ 个砖摆放好，使得他可以通过。有以下要求：\n\n1. ~~砖是有重力的~~，所以**一块砖只能摆放在下边界上或者另一块砖上**。同一横纵坐标不能摆放多块砖。\n2. 你至少要给 kid 留一条缝来通过，所以每一列你最高只能放 $m$ 块砖（地图高度为 $m+1$）。但是注意，ic 关卡下边界没有伤害，某一列是可以不放砖块的。\n3. kid 的跳跃能力和~~从高处坠落而不受伤的能力~~是有限的，这用一个非负整数 $k$ 来描述：相邻两列摆放的砖的数量之差的绝对值不能超过 $k$，否则该关卡对 kid 来说就是无解的。_（但是注意：该条对第一列高度没有要求，kid 出生点就在第一列。）_\n4. 你要把所有 $S$ 块砖都摆进去，不多不少。\n\nCreator 不会为难你，因此一定有一种关卡符合上述所有规则。\n\n为了输出方便，你只需要给出第 $i$ 列有多少砖块（记为 $a_i$），输出 $a$ 序列即可。容易证明，一个合法的 $a$ 序列和一个合法关卡是一一对应的。\n\n## Input\n\n仅一行 $4$ 个非负整数 $n,m,k,S$。\n\n## Output\n\n输出一行 $n$ 个非负整数表示你构造的序列 $a$。如果有多种可能的序列，输出任意一个符合题意的序列即可。**保证至少有一个序列满足题目要求。**\n\n[samples]\n\n## Background\n\n> ![](https://cdn.luogu.com.cn/upload/image_hosting/pon0cylv.png)\n\n## Note\n\n### 【数据范围】\n\n该题共有 $10$ 个测试点，每个测试点等分。\n\n- 对于 $20\\%$ 的数据，$S=n\\cdot m$。\n- 对于 $20\\%$ 的数据，$k=0$。\n- 对于 $20\\%$ 的数据，$k=10^9$。\n\n对于 $100\\%$ 的数据，$1\\leqslant n,m\\leqslant 10^5$，$0\\leqslant k\\leqslant 10^9$，$0\\leqslant S\\leqslant n\\cdot m$。\n\n### 【提示】\n> 古之有数，其名为 $S$。$S$ 之大，一个 `int` （可能）装不下。\n\n### 【样例解释 #1】\n样例输出对应关卡如下。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jyttdqal.png)\n\n注意可能有多种合法关卡均符合条件。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9429","tags":["Special Judge","O2优化","构造"],"sample_group":[["4 6 2 11","2 4 2 3"],["3 4 5 6","4 2 0"]],"created_at":"2026-03-03 11:09:25"}}