2015
05-23

# Iterated Difference

You are given a list of N non-negative integers a(1), a(2), … , a(N). You replace the given list by a new list: the k-th entry of the new list is the absolute value of a(k) – a(k+1), wrapping around at the end of the list (the k-th entry of the new list is the absolute value of a(N) – a(1)). How many iterations of this replacement are needed to arrive at a list in which every entry is the same integer?

For example, let N = 4 and start with the list (0 2 5 11). The successive iterations are:

2 3 6 11
1 3 5 9
2 2 4 8
0 2 4 6
2 2 2 6
0 0 4 4
0 4 0 4
4 4 4 4
Thus, 8 iterations are needed in this example.

The input will contain data for a number of test cases. For each case, there will be two lines of input. The first line will contain the integer N (2 <= N <= 20), the number of entries in the list. The second line will contain the list of integers, separated by one blank space. End of input will be indicated by N = 0.

The input will contain data for a number of test cases. For each case, there will be two lines of input. The first line will contain the integer N (2 <= N <= 20), the number of entries in the list. The second line will contain the list of integers, separated by one blank space. End of input will be indicated by N = 0.

4
0 2 5 11
5
0 2 5 11 3
4
300 8600 9000 4000
16
12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50
3
1 1 1
4
0 4 0 4
0

Case 1: 8 iterations
Case 2: not attained
Case 3: 3 iterations
Case 4: 50 iterations
Case 5: 0 iterations
Case 6: 1 iterations

//Time : 203MS
//Memory : 224K
#include <stdio.h>
int sum=-1;
int dif(int a[],int n)
{
int i,s=0;
bool zero=true;
sum++;
for(i=0;i<n-1;i++)
{	if(a[i]<0)
a[i]=0-a[i];
if(a[i+1]<0)
a[i+1]=0-a[i+1];
a[i]=a[i+1]-a[i];
if(a[i]!=0)
zero=false;
s+=a[i];
}
a[n-1]=s;
if(s==0 && zero)
return sum;
if(sum>1000)
return -1;
dif(a,n);
}
int main()
{
int a[21];
int n,temp=1;
while(scanf("%d",&n)!=EOF && n)
{
sum=-1;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int num=dif(a,n);
printf("Case %d: ",temp);
if(num==-1)
printf("not attained\n");
else
printf("%d iterations\n",num);
temp++;
}
return 0;
}