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
1in?
Each test case consists of two lines.
The first contains the number
n (
1n106), the number of integers in the sequence.
The second contains
n integers
a0,..., an-1 (
-1000ai1000) representing the sequence of numbers.
The input will finish with a line containing
0.
For each test case, print one line with the number of cyclic shifts of
the given sequence which satisfy the condition stated above.
3
2 2 1
3
-1 1 1
1
-1
0
3
2
0
#include<stdio.h>
ResponderEliminarlong min,a[1000006],i,n,x,j,t;
int main(){
scanf("%ld",&n);
while(n!=0){
min=t=0;
for(i=1;i<n;i++){
scanf("%ld",&x);
a[i]=a[i-1]+x;
if(a[i]<min){min=a[i]; j=i; }
}
scanf("%ld",&x);
a[n]=a[n-1]+x;
if(a[n]<0){
printf("0\n");
}else{
min+=a[n];
for(i=n-1;i>=j;i--){
if(a[i]<=min){
min=a[i];
t++;
}
}
printf("%ld\n",t);
}
scanf("%ld",&n);
}
}