均值 - 代码源竞赛平台

题目描述

仓库连续 $n$ 天接收货物，第 $i$ 天收到的件数为 $b_i$，每天可以收到 $0$ 至 $K$ 件。管理员在第 $i$ 天结束时，计算前 $i$ 天每天收到的平均件数，向下取整后记为 $a_i$。

现在只留下了整数数组 $a$。请构造一个长度为 $n$ 的整数数组 $b$，使得对每个 $1\le i\le n$，都有 $0\le b_i\le K$，且 $\left\lfloor\frac{b_1+b_2+\cdots+b_i}{i}\right\rfloor=a_i$。

其中，$\lfloor x\rfloor$ 表示不大于 $x$ 的最大整数。例如，$\left\lfloor\frac{5}{2}\right\rfloor=2$。

如果有多个满足条件的数组，输出任意一个。如果不存在，输出 $-1$。

输入格式

第一行包含两个正整数 $n$ 和 $K$，分别为记录的天数和每天接收货物件数的上限。

第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 为第 $i$ 天结束时记录的取整均值。

输出格式

若不存在满足条件的数组，输出一行一个整数 $-1$。

否则输出一行 $n$ 个非负整数 $b_1,b_2,\ldots,b_n$，表示每天接收货物的件数。每个数均须位于 $0$ 至 $K$，且所有记录都与数组 $a$ 相符。

样例

3 3
1 1 2

1 2 3

3 2
0 0 2

-1

样例解释

样例 1：三个前缀的平均值分别为 $1$、$1.5$、$2$，向下取整后得到 $1$、$1$、$2$。

样例 2：第二个前缀和至多为 $1$，再加入一个至多为 $2$ 的数后，总和至多为 $3$，无法使第三个前缀平均值达到 $2$。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$15$	$8$	A
$2$	$25$	$2000$	无
$3$	$20$	$2\times 10^5$	B
$4$	$40$		无

特殊性质 A：$K\le 3$。

特殊性质 B：$K=1$。

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le K\le 10^9$，$0\le a_i\le K$，输入均为整数。