2015 HUAS Summer Training#1 B

题目：

A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers (a₁, a₂,^..., a_n), the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers:

( a₁, a₂, ^..., a_n) (| a₁ - a₂|,| a₂ - a₃|, ^...,| a_n - a₁|)

Ducci sequences either reach a tuple of zeros or fall into a periodic loop. For example, the 4-tuple sequence starting with 8,11,2,7 takes 5 steps to reach the zeros tuple:

(8, 11, 2, 7)

(3, 9, 5, 1)

(6, 4, 4, 2)

(2, 0, 2, 4)

(2, 2, 2, 2)

(0, 0, 0, 0).

The 5-tuple sequence starting with 4,2,0,2,0 enters a loop after 2 steps:

(4, 2, 0, 2, 0)

(2, 2, 2, 2, 4)

( 0, 0, 0, 2, 2)

(0, 0, 2, 0, 2)

(0, 2, 2, 2, 2)

(2, 0, 0, 0, 2)

(2, 0, 0, 2, 0)

(2, 0, 2, 2, 2)

(2, 2, 0, 0, 0)

(0, 2, 0, 0, 2)

(2, 2, 0, 2, 2)

(0, 2, 2, 0, 0)

(2, 0, 2, 0, 0)

(2, 2, 2, 0, 2)

(0, 0, 2, 2, 0)

(0, 2, 0, 2, 0)

(2, 2, 2, 2, 0)

( 0, 0, 0, 2, 2)

^...

Given an n-tuple of integers, write a program to decide if the sequence is reaching to a zeros tuple or a periodic loop.

Input

Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n(3n15), which represents the size of a tuple in the Ducci sequences. In the following line, n integers are given which represents the n-tuple of integers. The range of integers are from 0 to 1,000. You may assume that the maximum number of steps of a Ducci sequence reaching zeros tuple or making a loop does not exceed 1,000.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print `LOOP' if the Ducci sequence falls into a periodic loop, print `ZERO' if the Ducci sequence reaches to a zeros tuple.

The following shows sample input and output for four test cases.

题目大意：给你N个数，用( a₁, a₂, ^..., a_n) (| a₁ - a₂|,| a₂ - a₃|, ^...,| a_n - a₁|)在1000次计算里找它的是否循环是输出LOOP 否输出ZERO；

解题思路：用vector数组存储这些数在进行比较；

代码：

 1 #include<iostream>
 2 #include<math.h>
 3 #include<vector>
 4 using namespace std;
 5 const  int l=1000+10;
 6 
 7 int main()
 8 {
 9     vector<int> a[l];
10     vector<int> b;
11     int    T,n,i,t,j,d,p;
12     cin>>T;
13     while(T--)
14     {
15         cin>>n;
16         if(n>=3&&n<=15)
17         {
18             d=0;
19             b.resize(n);
20             for(i=0;i<l;i++)
21                 a[i].resize(n);
22             for( i=0;i<n;i++)
23             {
24                 scanf("%d",&a[0][i]);
25                 b[i]=0;
26                 if(a[0][i]<0||a[0][i]>1000)
27                     scanf("%d",&a[0][i]);
28             }
29             for(i=0;i<1000;i++) 
30             {
31                 t=a[i][0];
32                 for(j=0;j<n;j++) 
33                 {        
34                     if(j==(n-1))
35                         a[i+1][j]=abs(a[i][n-1]-t); 
36                     else 
37                         a[i+1][j]=abs(a[i][j]-a[i][j+1]);
38                 }
39                 if(a[i+1]==b)
40                 {
41                     printf("ZERO
");
42                     d=i;
43                     break;
44                 }
45             }
46             if(d==0)
47                 printf("LOOP
");        
48         }                
49     }
50     return 0;