问题1046--非负和

1046: 非负和

时间限制: 1 Sec  内存限制: 128 MB
提交: 131  解决: 50
[提交] [状态] [讨论版] [命题人:]

题目描述

罗老师给大家n个数字:a1,a2,a3, .. , an

这些数字可以循环,ai, ai+1, ai+2, … , an, a1, a2, … , ai-1

显然,这样的循环有n种。

现在问大家,n种中有多少种保证从第一项到任意项的和大于等于0

比如

3

-1 1 1

有三种:

-1 1 1

1 1 -1

1 -1 1

其中第一种第一项到第1,2,3项的和分别为: -1 0 1

第二种第一项到第1,2,3项的和分别为: 1 2 1

第三种第一项到第1,2,3项的和分别为: 1 0 1

所以第二种和第三种符合,答案为2

输入

输入n

然后输入n个数字ai

输出

输出有多少种符合

样例输入 Copy

3
-1 1 1

样例输出 Copy

2

提示

【数据规模和约定】

1<=n<=1000000

-1000<=ai<=1000

来源/分类