PARSUMS - Nonnegative Partial Sums
You are given a sequence of n numbers a0, …, an−1. A cyclic shift by k positions (0 ≤ k ≤ n−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 ≤ i ≤ n?
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
M@@Y@:
2011-12-03 06:03:16
@Raja .... its " How many of the n cyclic shifts " ...i guess i m making things clear. |
|
R@ja.... -[^_^]-:
2011-11-30 03:37:14
how come the output for 1st case is 3...will 0 shift not do..???? pl help.. Last edit: 2011-11-30 03:38:09 |
|
Kazi Rakibul Hossain:
2011-11-27 18:48:40
nice problem :) |
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 |