YoungProgrammer

Lesson: 42
Problem: 2891
Title: "Sub"-Sequence
Difficulty Level: 2.0
Date: MAR 03, 2009
Site: http://acm.tju.edu.cn/toj/showp2891.html

Lets consider the first sample input
1 2 3 4
Find the difference between each pair of adjacent elements..
1 1 1 ( that is, 2-1 = 1, 3-2 = 1 and 4-1 = 1)
Repeat this process again, we get
0 0 (as 1 - 1 = 0, 1 - 1 = 0)
Repeat again, we get only one number,
0 (as 0 - 0 = 0)

So, output is 0

How many step do we need to find the final number among N numbers ? Ans is: N - 1 steps. That's why we need 3 steps for 4 numbers
in the first sample input.

#include<stdio.h>
#define maxn 22

int A[maxn];

void Find(int n) {
	int i, j;
	for(i = n; i >=2; i--) {
		for( j = 1; j<i; j++) {
			A[j] = A[j+1] - A[j];
		}
	}
	printf("%d\n",A[1]);
}


int main() {
	int kase, n;
	scanf("%d",&kase);
	while(kase--) {
		scanf("%d",&n);
		for(int i = 1; i<= n; i++) {
			scanf("%d",&A[i]);
		}
		Find(n);
	}
	return 0;
}