[USACO20JAN] Photoshoot B

Luogu

IDLGP9947

Time1000ms

Memory256MB

DifficultyP2

模拟2020USACOO2优化枚举

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$。 ## Input 输入的第一行包含一个整数 $N$。第二行包含 $N−1$ 个空格分隔的整数 $b_1,b_2,\ldots,b_{N−1}$。 ## Output 输出一行，包含 $N$ 个空格分隔的整数 $a_1,a_2,\ldots,a_N$。 [samples] ## Note ### 样例解释 1 $a$ 能够产生 $b$，因为 $3+1=4$，$1+5=6$，$5+2=7$，$2+4=6$。 ### 测试点性质 - 测试点 $2-4$ 满足 $N\le 8$。 - 测试点 $5-10$ 没有额外限制。

Samples

Input #1

5
4 6 7 6

Output #1

3 1 5 2 4

API Response (JSON)

{
  "problem": {
    "name": "[USACO20JAN] Photoshoot B",
    "description": {
      "content": "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 仍然有机会恢复他之前写下的排列。在这张纸被偷走之前，Bessi",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9947"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 偷走了！\n\n幸好 FJ 仍然有机会恢复他之前写下的排列。在这张纸被偷走之前，Bessi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments