Rain Flows into Dams

题目描述

圆周上有 $N$ 座山，按顺时针方向分别称为山峰 $1$、山峰 $2$、...、山峰 $N$。$N$ 是一个奇数。 这些山之间有 $N$ 个水坝，称为坝 $1$、坝 $2$、...、坝 $N$。坝 $i$（$1 \leq i \leq N$）位于山峰 $i$ 和 $i+1$ 之间（山峰 $N+1$ 为山峰 $1$）。 当山峰 $i$（$1 \leq i \leq N$）收到 $2x$ 升雨水时，坝 $i-1$ 和 坝 $i$ 各自积累 $x$ 升水（坝 $0$ 为坝 $N$）。 某天，每座山收到的雨量是一个非负的偶数升。 结果，坝 $i$（$1 \leq i \leq N$）累计了 $A_i$ 升水。 求每座山收到的雨量。在本题约束下可以证明解是唯一的。

输入格式

输入从标准输入给出，格式如下： $N$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出 $N$ 个整数，表示山峰 $1$、山峰 $2$、...、山峰 $N$ 收到的雨量（升），按此顺序。

3
2 2 4

4 0 4

5
3 8 7 5 5

2 4 12 2 8

3
1000000000 1000000000 0

0 2000000000 0

提示

输入中的所有值均为整数。 $3 \leq N \leq 10^5-1$ $N$ 为奇数。 $0 \leq A_i \leq 10^9$ 输入所表示的情况可以在每座山收到非负偶数升雨的情况下发生。如果我们假设山峰 $1$、$2$、$3$ 分别收到 $4$、$0$、$4$ 升雨水，则与此输入一致，如下所示：

坝 $1$ 应该积累 $\frac{4}{2} + \frac{0}{2} = 2$ 升水。 坝 $2$ 应该积累 $\frac{0}{2} + \frac{4}{2} = 2$ 升水。 坝 $3$ 应该积累 $\frac{4}{2} + \frac{4}{2} = 4$ 升水。

标签: AtCoder|abc133D

来源

AtCoder|abc133D