PARSUMS - Nonnegative Partial Sums

no tags 

You are given a sequence of n numbers a0, …, an−1. A cyclic shift by k positions (0 ≤ kn−1) results in the following sequence: ak, ak+1, …, an−1, a0, a1, …, ak−1. How many of the n cyclic shifts satisfy the condition that the sum of the first i numbers is greater than or equal to zero for all i with 1 ≤ in?



Input

Each test case consists of two lines. The first contains the number n (1 ≤ n ≤ 106), the number of integers in the sequence. The second contains n integers a0, …, an−1 (−1000 ≤ ai ≤ 1000) representing the sequence of numbers. The input will finish with a line containing 0.



Output

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.



Sample Input

3
2 2 1
3
-1 1 1
1
-1
0



Sample Output

3
2
0

Problemsetter: Adrian Kuegel

hide comments
Sahil Sharma: 2015-01-13 07:13:57

Hi,

Could someone please tell me about how one can get a solution as fast as under 1 second for this problem? Are there some algorithm level optimizations for this problem? My algorithm is O(n)(with a reasonably small constant) and also uses fast Input (getchar() based) and yet it takes 6.6 seconds.

Thanks

AlcatraZ: 2014-04-22 23:11:32

Nice and Tricky.. ;)

Ankit Jain: 2014-01-04 13:21:55

logical question

BOND: 2011-12-22 17:26:35

@accept
first i numbers mean every number starting from base index till i
if 1 is your base index then yes,otherwise by default it starts with index 0

accept: 2011-12-22 10:54:07

what's mean of first i number..
is this number start from 1 or random..

BOND: 2011-12-21 15:54:38

edit- got it

Last edit: 2012-05-26 12:50:59
Adrian Kuegel: 2011-12-15 14:32:28

Please tell which part is unclear to you.
Here is an example: If the original sequence is -1 1 1,
then there are 3 cyclic shifts: shift by 0 positions results in -1 1 1, shift by 1 positions results in 1 1 -1, shift by 2 positions results in 1 -1 1.

Last edit: 2011-12-15 14:35:20
Vratika Ghatiya: 2011-12-15 14:24:20

Please elaborate i !!
For 0 Shift we have to check -1 >= 0 , for 1st shift 1+1 >=0 and for 2nd shift 1+(-1)+1 >= 0 , is it so..??

Last edit: 2011-12-16 08:55:09
sri: 2011-12-03 09:34:10

what is the value of i???
could not understand the question properly..

M@@Y@: 2011-12-03 06:03:16

@Raja .... its " How many of the n cyclic shifts " ...i guess i m making things clear.


Added by:David GarcĂ­a Soriano
Date:2011-11-26
Time limit:8.989s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Southwestern Europe Regional, SWERC 2011