分数: 300 点
问题陈述
高桥在坐标 数轴上的 0.5 。
他将使 N 移动。
在 i第一步,他选择正方向或负方向,然后移动 L_i 朝那个方向。
他最多可以通过坐标多少次 0?
在这个问题的约束下,没有移动会在坐标处结束 0.
约束
- 1 \le N \le 20
- 1 \le L_i \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N L_1 L_2 \dots L_N
输出
输出答案。
示例输入 1
5 2 5 2 2 1
示例输出 1
4
例如,通过选择如下运动方向,他可以通过坐标 0 四次,这是最大值。
- 在第一次移动中,选择负方向并移动 2。他从坐标移动 0.5 to -1.5,通过坐标 0.
- 第二次移动时,选择正方向并移动 5。他从坐标移动 -1.5 to 3.5,通过坐标 0.
- 第三步,选择负方向并移动 2。他从坐标移动 3.5 to 1.5.
- 第四步,选择负方向并移动 2。他从坐标移动 1.5 to -0.5,通过坐标 0.
- 第五步,选择正方向并移动 1。他从坐标移动 -0.5 to 0.5,通过坐标 0.
示例输入 2
5 100 1 2 3 4
示例输出 2
1
示例输入 3
20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
示例输出 3
20