두치수열 > 문제은행



문제은행

1486 : 두치수열

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 3 회    시도횟수: 3 회   



두치수열이란? n개의 원소로 이루어진 집합들의 수열이다.
n개의 정수로 이루어진 집합(a1, a2, a3, ... , an)이 주어졌을 때, 이 집합의 다음 단계로 생성되는 집합은 다음과 같다.
(|a1-a2|, |a2-a3|, ... ,|an-a1|)

두치수열은 모든 원소가 0이 되거나, 동일한 집합이 주기적으로 반복되는 겨우 2가지로 나누어진다.

예를 들어, (8,11,2,7)의 경우에는 다음과 같은 과정을 거쳐 모든 원소가 0이된다.
(8,11,2,7)->(3,9,5,1)->(6,4,4,2)->(2,0,2,4)->(2,2,2,2)->(0,0,0,0)

(4,2,0,2,0)의 경우 2번째 단계의 집합이 다음에도 등장하며, 주기성을 가지게 된다.
(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)->...

n개의 정수로 이루어진 집합이 주어졌을 때, 이 집합이 위의 과정을 거쳤을 때, 모두 0이 되는지, 아니면 주기성을 가지는지를 판단하는 프로그램을 작성하라.




입력의 첫번째 줄에는 테스트 케이스의 개수 T(T≤10)가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 n(3≤n≤15)이 입력된다.
그 다음 줄에는 n개의 집합을 이루는 정수가 입력되며, 이는 0이상 1,000이하의 정수다.
각 테스트 케이스는 1,000번 이내에 모두 0이 되거나 주기성을 가지게 된다고 가정한다.




각 테스트 케이스에 대해, 모두 0이 될 경우 "ZERO"를, 주기성을 가질 경우 "LOOP"를, " "를 제외하고 출력한다.



4
4
8 11 2 7
5
4 2 0 2 0
7
0 0 0 0 0 0 0
6
1 2 3 1 2 3
ZERO
LOOP
ZERO
LOOP


출처 : uva 1594




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.