← 返回题目列表

AtCoder · joig2023_b

B. 绝对差值序列

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI 高中生 Aoi 喜欢思考数字序列,其中相邻项之间的差的绝对值按顺序排列。

一开始,长度是写在黑板上的。 N 序列 给出了 A_1,A_2,\ldots,A_N 上写着。

Aoi 执行以下操作。 重复 N-1 次。

  • 黑板上写的数列长度为 m 序列是 假设 b_1,b_2,\ldots,b_m 。 黑板上写的数字顺序 删除 b_1,b_2,\ldots,b_m 和长度 在黑板上写下 m-1 序列 给出了 |b_1-b_2|,|b_2-b_3|,\ldots,|b_{m-1}-b_m| 。然而, 表示|x| 是 它仅由 x 的绝对值。

N-1 操作完成后,将显示黑板。 1 两个值(长度 1 序列)被写入。

最初给出了黑板上写的数列的信息,所以 编写一个程序,在完成N-1 操作后查找黑板上写的值。 完成

制約

  • 2 \leqq N \leqq 2\,000.
  • 0 \leqq A_i \leqq 10^9.
  • 所有输入值都是整数。

小課題

  1. (25 点) N=2.
  2. (75 点)没有额外的限制。

入力

输入按照以下格式给出。

N
A_1 A_2 \cdots A_N

出力

N-1 运算后,输出黑板上写的值。


入力例 1

4
3 1 4 1

出力例 1

1

一开始,长度就在黑板上。 4 序列 给出了 3,1,4,1 上写着。

葵是 执行 (4-1=)3 操作。

  • 1 在第二次操作中,长度为 写入 4 序列 给出了 3,1,4,1 和长度 在黑板上写下 3 序列 给出了 2,3,3 。
  • 2 在第二次操作中,长度为 写入 3 序列 给出了 2,3,3 和长度 在黑板上写下 2 序列 给出了 1,0 。
  • 3 在第二次操作中,长度为 写入 2 序列 给出了 1,0 和长度 在黑板上写下 1 序列 给出了 1 。

3 完成运算后黑板上写下的值为 1 ,所以1 。

此输入示例是一个小作业。 2 满足约束。


入力例 2

2
2 4

出力例 2

2

此输入示例满足所有子任务约束。


入力例 3

6
2 7 5 3 3 11

出力例 3

3

此输入示例是一个小作业。 2 满足约束。


入力例 4

10
3 1 4 1 5 9 2 6 5 3

出力例 4

0

此输入示例是一个小作业。 2 满足约束。


入力例 5

2
0 0

出力例 5

0

此输入示例满足所有子任务约束。