← 返回题目列表

Codeforces · 895/A

A. 披萨分离

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

学生 Vasya 和 Petya 正在 BSU(Byteland 州立大学)学习。有一次休息时,他们决定点一份披萨。在这个问题中,披萨是一个具有一定半径的圆。送来的披萨已经被切成n块了。第 i 块是角度等于 ai 的扇形。 Vasya 和 Petya 想要将所有披萨片分成两个连续的扇区,使这些扇区的角度之间的差异最小。扇形角是其中所有扇形的角度之和。请注意,其中一个扇区可以为​​空。

输入

第一行包含一个整数 n (1 ≤ n ≤ 360) — 交付的披萨被切成的块数。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 360) — 披萨被切割成的扇区的角度。所有ai的总和是360。

输出

打印一个整数——前往 Vasya 和 Petya 的扇区角度之间的最小差异。

示例

输入 #1

4
90 90 90 90

输出 #1

0

输入 #2

3
100 100 160

输出 #2

40

输入 #3

1
360

输出 #3

360

输入#4

4
170 30 150 10

输出#4

0

注意

在第一个样本中,Vasya 可以拿 1 件和 2 件,Petya 可以拿 3 件和 4 件。那么答案就是 |(90 + 90) - (90 + 90)| = 0。

在第三个样本中,只有一张披萨只能由 Vasya 和 Petya 中的一个人拿走。所以答案是 |360 - 0| = 360。

在第四个样本中,Vasya 可以拿走 1 和 4 件,然后 Petya 将拿走 2 和 3 件。所以答案是 |(170 + 10) - (30 + 150)| = 0。

解释第四个示例的图片:

红色和绿色部分均由两块相邻的披萨组成。因此 Vasya 可以占据绿色区域,然后 Petya 可以占据红色区域。