ACM-ICPC 2010년도 O.T. 문제 1 - Ducci Sequence

Programming/Algorithm 2010.10.04 14:18

A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers , the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers:
Ducci sequences either reach a tuple of zeros or fall into a periodic loop. For example, the 4-tuple sequence starting with 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 enters a loop after 2 steps:
Given an n-tuple of integers, write a program to decide if the sequence is reaching to a zeros tuple or a periodic loop.


Your program is to read the input from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. Each test case starts with a line containing an integer , which represents the size of a tuple in the Ducci sequences. In the following line, integers are given which represents the n-tuple of integers. The range of integers are from to . 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.


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.

Sample Input

8 11 2 7
4 2 0 2 0
0 0 0 0 0 0 0
1 2 3 1 2 3

Output for the Sample Input


비교적 간단한 문제.
그냥 설명 써진대로 수열 만들면 된다.