CF732B Cormen — The Best Friend Of a Man

最近，Polycarp 买了一条狗，这条狗的名字叫 Cormen。现在，Polycarp 遇到了很多麻烦。例如，Cormen 很喜欢出去散步。 Polycarp 通过经验得知，为了让狗狗感觉良好，对任意相邻的两天，散步的总次数至少要有 $k$ 次。例如，如果 $k=5$ 并且昨天 Polycarp 带 Cormen 散步了 $2$ 次，那么今天他至少要再带狗狗散步 $3$ 次。 Polycarp 对接下来 $n$ 天的所有事务进行了分析，并得到了一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 代表在第 $i$ 天由于各种事务（比如去商店、扔垃圾等）他会和 Cormen 一起散步的次数。 请你帮 Polycarp 计算，在接下来的 $n$ 天内，他至少还需要额外散步多少次，才能让 Cormen 在所有 $n$ 天内都感觉良好。此外，请输出对应的散步安排——一个长度为 $n$ 的序列 $b_1,b_2,\ldots, b_n$（$b_i \geq a_i$），其中 $b_i$ 表示第 $i$ 天实际和狗狗散步的总次数。 你可以假定，在第一天的前一天以及第 $n$ 天的后一天，Polycarp 都会带 Cormen 散步恰好 $k$ 次。 写一个程序，找出最少需要补充的散步次数以及合理的每日安排。如果有多组答案，输出任意一组即可。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 500$），分别表示天数以及任意相邻两天所需的最小散步次数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_i \leq 500$），表示 Polycarp 计划在第 $i$ 天与 Cormen 散步的次数。

第一行输出最少需要额外补充的散步次数。 第二行输出 $n$ 个整数 $b_1,b_2,\ldots,b_n$，表示第 $i$ 天实际散步的总次数（满足 $a_i\leq b_i$，且任意相邻两天 $b_{i-1}+b_i \geq k$）。如果有多种答案，输出任意一组。

由 ChatGPT 5 翻译