P5226: 照相
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
Farmer John 在给他编号为 1…N
的 N
头奶牛排队拍照（2≤N≤10
3 ）。FJ 一开始计划从左向右数第 i
个位置排编号为 ai
的奶牛，他在一张纸上写下了排列 a1,a2,…,aN
。不幸的是，这张纸刚刚被 Farmer Nhoj 偷走了！
幸好 FJ 仍然有机会恢复他之前写下的排列。在这张纸被偷走之前，Bessie 记录了序列 b1,b2,…,bN−1 ，对于每一个 1≤i<N 满足 bi=ai+ai+1 。
基于 Bessie 的信息，帮助 FJ 恢复可以产生序列 b 的“字典序最小”的排列 a 。排列 x 字典序小于排列 y ，如果对于某个 j ，对于所有 i<j 均有 xi=yi ，且有 xj<yj （换句话说，这两个排列到某个位置之前都相同，在这个位置上 x 小于 y ）。保证存在至少一个满足条件的 a 。
测试点性质：
-
测试点 2-4 满足 N≤8 。
-
测试点 5-10 没有额外限制。
输入格式（文件名：photo.in）：
输入的第一行包含一个整数 N 。
第二行包含 N−1 个空格分隔的整数 b1,b2,…,bN−1 。
输出格式（文件名：photo.out）：
输出一行，包含 N 个空格分隔的整数 a1,a2,…,aN 。
输入样例：
5
4 6 7 6
输出样例：
3 1 5 2 4
a 能够产生 b ，因为 3+1=4 ，1+5=6 ，5+2=7 ，2+4=6 。