Photoshoot

题目描述

农夫 John 正在把他的 $N$ 头奶牛（$2\le N\le 10^3$），编号为 $1\ldots N$，排成一排拍照。FJ 最初计划从左往右第 $i$ 头奶牛是编号为 $a_i$ 的奶牛，并把排列 $a_1,a_2,\ldots,a_N$ 写在一张纸上。不幸的是，那张纸最近被农夫 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$。若存在某个 $j$ 使得对所有 $i<j$ 有 $x_i=y_i$ 且 $x_j<y_j$（换句话说，两个排列在某个位置之前完全相同，而在该位置 $x$ 更小），则称排列 $x$ 的字典序小于排列 $y$。保证至少存在一个满足条件的 $a$。

输入格式

第一行输入一个整数 $N$。 第二行输入 $N-1$ 个用空格分隔的整数 $b_1,b_2,\ldots,b_{N-1}$。

输出格式

输出一行，包含 $N$ 个用空格分隔的整数 $a_1,a_2,\ldots,a_{N}$。

5
4 6 7 6

3 1 5 2 4

提示

评分： 测试点 2-4 满足 $N\le 8$。 测试点 5-10 无额外限制。

$a$ 产生 $b$，因为 $3+1=4$，$1+5=6$，$5+2=7$，并且 $2+4=6$。 题目贡献：Benjamin Qi and Chris Zhang

标签: USACO|2020|Bronze

来源

USACO|2020|Bronze