3331. [USACO20 Jan Bronze]Photoshoot

【题目描述】

Farmer John 在给他编号为 $1\ldots N$ 的 $N$ 头奶牛排队拍照（$2\le N\le 10^3$）。FJ 一开始计划从左向右数第 $i$ 个位置排编号为 $a_i$ 的奶牛，他在一张纸上写下了排列 $a_1,a_2,\ldots,a_N$。不幸的是，这张纸刚刚被 Farmer Nhoj 偷走了！

幸好 FJ 仍然有机会恢复他之前写下的排列。在这张纸被偷走之前，Bessie 记录了序列 $b_1,b_2,\ldots,b_{N-1}$，对于每一个 $1\le i<N$ 满足 $b_i=a_i+a_{i+1}$。

基于 Bessie 的信息，帮助 FJ 恢复可以产生序列 $b$ 的“字典序最小”的排列 $a$。排列 $x$ 字典序小于排列 $y$，如果对于某个 $j$，对于所有 $i<j$ 均有 $x_i=y_i$，且有 $x_j<y_j$（换句话说，这两个排列到某个位置之前都相同，在这个位置上 $x$ 小于 $y$）。

保证存在至少一个满足条件的 $a$。

【输入格式】

输入的第一行包含一个整数$ N $。

第二行包含$ N - 1 $个以空格分隔的整数$ b_1，b_2，…，b_{N - 1} $。

【输出格式】

具有$ N $个以空格分隔的整数$ a_1，a_2，…，a_N $的单行。

【样例输入】

5
4 6 7 6

【样例输出】

3 1 5 2 4

【样例解释】

序列$ a $产生序列$ b $是因为$ 3 + 1 = 4、1 + 5 = 6、5 + 2 = 7 $和$ 2 + 4 = 6 $

【提示】

对于$ 40\% $的测试数据(测试点$ 1\sim4 $)，满足$ N ≤ 8 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Bronze 组