toj_2891.cpp

Tianjin University Online Judge 的80多道题目 .

/*2891.   "Sub"-Sequence Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 132   Accepted Runs: 94


Given a sequence which contains n elements, we can get its "Sub"-sequence by taking the difference between each pair of adjacent elements. For instance, the original sequence is a1, a2... an, and its "Sub"-sequence is b1, b2... bn-1, where bi = ai+1 - ai.

Now we iteratively apply the above process several times until there is only one element in the sequence. Please write a program to calculate the last element left in the "Sub"-sequence.

Input:

There are several test cases in the input data. The first line contains the number of test cases. There are two lines in each test case. The first line contains a positive integer N (1 ≤ N ≤ 20) denoting the length of the original sequence. The second line contains a sequence of N elements separated by spaces. It is guaranteed that the absolute value of every element will not exceed 100.

Output:

Output the last element left in the "Sub"-sequence in one line for every test case.

Sample input:

20
4
1 2 3 4
5
12 -5 3 -100 8

Sample output:

0
458



Source: TJU Exam 2007*/
#include<cstdio>
int main()
{
  int nOfCase , n , num[ 2 ][ 20 ] , i , j , k , flag;
  scanf( "%d" , &nOfCase );
  for ( i = 0; i < nOfCase; i++ )
    {
      scanf( "%d" , &n );
      for ( j = 0; j < n; j++ )
	{
	  scanf( "%d" , &num[ 0 ][ j ] );
	}
      for ( flag = 0  , j = n - 2 ; j >= 0 ; j-- , flag = 1 - flag )
	{
	  for ( k = j ; k >= 0 ; k-- )
	    {
	      num[ 1 - flag ][ k ] = num[ flag ][ k + 1 ] - num[ flag ][ k ];
	    }
	  printf( "\n" );
	}
      printf( "%d\n" , num[ flag ][ 0 ] );
    }
  return 0;
}