← 返回题目列表

AtCoder · code_thanks_festival_2018_h

H. 中值游戏

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

配点 : 500 点

問題文

如果整数是 1 一张一张写的卡片 N 纸张从顶部开始堆叠。 i 第二个是 写入 a_{i} 。

Alice 和 Bob 决定使用这些卡片玩游戏。

2 人们从爱丽丝开始,轮流从顶部拿起剩余的卡片。 1 取多少块,记下此时取的整数之和。

当没有剩余牌时,使用写出的整数计算本场比赛的分数。

写出的整数个数为 K 从最小的开始 本场比赛的得分为大于或等于 (K+1)/2 的最小整数。

2 该人事先知道卡上写的号码。 Alice想让游戏得分尽可能高,而Bob则想让游戏得分尽可能小。

2 当大家都发挥最好的时候,这场比赛的得分是多少?

制約

  • 1 \leq N \leq 1000
  • 0 \leq |a_i| \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
a_1 a_2 ... a_{N-1} a_N

出力

2 当该人做出最佳投注时打印游戏得分。


入力例 1

2
1 -1

出力例 1

1

爱丽丝第一 如果我们取 \{1, -1\} ,写入的整数是 \{0\} 得分为 0 。 爱丽丝第一 采取 \{1\} ,鲍勃有 \{-1\} 写入的整数是 \{1, -1\} 得分为 1 。

因此,对于爱丽丝 最好选择 \{1\} ,分数为 1 。


入力例 2

3
3 1 4

出力例 2

8