시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 276 149 121 63.021%

문제

두찌 수열은 정수 n-튜플로 이루어진 수열이다. 정수 n-튜플 (a1, a2, ..., an)이 주어졌을 때, 수열에서 다음 수는 인접한 숫자 간의 차이이다.

(a1, a2, ..., an) -> (|a1-a2|, |a2-a3|, ..., |an-a1|)

두찌 수열은 항상 0으로 이루어진 튜플이 나오거나 주기적인 루프를 만나게 된다. 예를 들어, (8, 11, 2, 7)로 시작한 수열은 다음과 같이 5번 만에 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가 주어진다. 각 테스트 케이스의 첫째 줄에는 튜플의 크기 n이 주어진다. (3 ≤ n ≤ 15) 다음 줄에는 n튜플이 주어진다. 주어지는 수는 모두 0보다 크거나 같고, 1000보다 작거나 같다. 두찌 수열이 0을 만나거나, 루프를 만드는데 필요한 최대 단계수는 1,000을 넘지 않는다.

출력

두찌 수열이 루프에 빠지는 경우에는 LOOP, 0을 만나는 경우에는 ZERO를 출력한다.

예제 입력 1

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

예제 출력 1

ZERO
LOOP
ZERO
LOOP
W3sicHJvYmxlbV9pZCI6Ijg5MjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTBcdWNjMGMgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTBcdWNjMGMgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YzgxNVx1YzIxOCBuLVx1ZDI5Y1x1ZDUwY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc0XHViMmU0LiBcdWM4MTVcdWMyMTggbi1cdWQyOWNcdWQ1MGMgKGExLCBhMiwgLi4uLCBhbilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yzc0YyBcdWMyMThcdWIyOTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YzIyYlx1Yzc5MCBcdWFjMDRcdWM3NTggXHVjYzI4XHVjNzc0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4oYTEsIGEyLCAuLi4sIGFuKSAtJmd0OyAofGExLWEyfCwgfGEyLWEzfCwgLi4uLCB8YW4tYTF8KTxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWNjMGMgXHVjMjE4XHVjNWY0XHVjNzQwIFx1ZDU2ZFx1YzBjMSAwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyOWNcdWQ1MGNcdWM3NzQgXHViMDk4XHVjNjI0XHVhYzcwXHViMDk4IFx1YzhmY1x1YWUzMFx1YzgwMVx1Yzc3OCBcdWI4ZThcdWQ1MDRcdWI5N2MgXHViOWNjXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgKDgsIDExLCAyLCA3KVx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgNVx1YmM4OCBcdWI5Y2NcdWM1ZDAgMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMjljXHVkNTBjXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+KDgsMTEsMiw3KSAtJmd0OyAoMyw5LDUsMSkgLSZndDsgKDYsNCw0LDIpIC0mZ3Q7ICgyLDAsMiw0KSAtJmd0OyAoMiwyLDIsMikgLSZndDsgKDAsMCwwLDApPFwvcD5cclxuXHJcbjxwPig0LDIsMCwyLDApXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NDAgMlx1YjJlOFx1YWNjNCBcdWI5Y2NcdWM1ZDAgXHVjOGZjXHVhZTMwXHVjODAxXHVjNzc4IFx1YjhlOFx1ZDUwNFx1YzVkMCBcdWJlNjBcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPig0LDIsMCwyLDApIC0mZ3Q7ICgyLDIsMiwyLDQpIC0mZ3Q7ICgwLDAsMCwyLDIpIC0mZ3Q7ICgwLDAsMiwwLDIpIC0mZ3Q7ICgwLDIsMiwyLDIpIC0mZ3Q7ICgyLDAsMCwwLDIpIC0mZ3Q7PGJyIFwvPlxyXG4oMiwwLDAsMiwwKSAtJmd0OyAoMiwwLDIsMiwyKSAtJmd0OyAoMiwyLDAsMCwwKSAtJmd0OyAoMCwyLDAsMCwyKSAtJmd0OyAoMiwyLDAsMiwyKSAtJmd0OyAoMCwyLDIsMCwwKSAtJmd0OzxiciBcLz5cclxuKDIsMCwyLDAsMCkgLSZndDsgKDIsMiwyLDAsMikgLSZndDsgKDAsMCwyLDIsMCkgLSZndDsgKDAsMiwwLDIsMCkgLSZndDsgKDIsMiwyLDIsMCkgLSZndDsgKDAsMCwwLDIsMikgLSZndDsgLi4uPFwvcD5cclxuXHJcbjxwPm5cdWQyOWNcdWQ1MGNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1ZDI5Y1x1ZDUwY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzc0IDBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDI5Y1x1ZDUwY1x1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWM5YzAsIFx1YzhmY1x1YWUzMFx1YzgwMVx1Yzc3OCBcdWI4ZThcdWQ1MDRcdWM1ZDAgXHViZTYwXHVjOWMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyOWNcdWQ1MGNcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IG4gJmxlOyAxNSkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVkMjljXHVkNTBjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjQ1MFx1Y2MwYyBcdWMyMThcdWM1ZjRcdWM3NzQgMFx1Yzc0NCBcdWI5Y2NcdWIwOThcdWFjNzBcdWIwOTgsIFx1YjhlOFx1ZDUwNFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YjMwMCBcdWIyZThcdWFjYzRcdWMyMThcdWIyOTQgMSwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI0NTBcdWNjMGMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YjhlOFx1ZDUwNFx1YzVkMCBcdWJlNjBcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IExPT1AsIDBcdWM3NDQgXHViOWNjXHViMDk4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBaRVJPXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4OTIyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRHVjY2kgU2VxdWVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkEgRHVjY2kgc2VxdWVuY2UgaXMgYSBzZXF1ZW5jZSBvZiBuLXR1cGxlcyBvZiBpbnRlZ2Vycy4gR2l2ZW4gYW4gbi10dXBsZSBvZiBpbnRlZ2VycyZuYnNwOyhhMSwgYTIsIC4uLiwgYW4pLCB0aGUgbmV4dCBuLXR1cGxlIGluIHRoZSBzZXF1ZW5jZSBpcyBmb3JtZWQgYnkgdGFraW5nIHRoZSBhYnNvbHV0ZSBkaWZmZXJlbmNlcyBvZiBuZWlnaGJvcmluZyBpbnRlZ2Vyczo8XC9wPlxyXG5cclxuPHA+KGExLCBhMiwgLi4uLCBhbikgLSZndDsgKHxhMS1hMnwsIHxhMi1hM3wsIC4uLiwgfGFuLWExfCk8XC9wPlxyXG5cclxuPHA+RHVjY2kgc2VxdWVuY2VzIGVpdGhlciByZWFjaCBhIHR1cGxlIG9mIHplcm9zIG9yIGZhbGwgaW50byBhIHBlcmlvZGljIGxvb3AuIEZvciBleGFtcGxlLCB0aGUgNC10dXBsZSBzZXF1ZW5jZSBzdGFydGluZyB3aXRoIDgsMTEsMiw3IHRha2VzIDUgc3RlcHMgdG8gcmVhY2ggdGhlIHplcm9zIHR1cGxlOjxcL3A+XHJcblxyXG48cD4oOCwxMSwyLDcpICZyYXJyOyAoMyw5LDUsMSkgJnJhcnI7ICg2LDQsNCwyKSAmcmFycjsgKDIsMCwyLDQpICZyYXJyOyAoMiwyLDIsMikgJnJhcnI7ICgwLDAsMCwwKS48XC9wPlxyXG5cclxuPHA+VGhlIDUtdHVwbGUgc2VxdWVuY2Ugc3RhcnRpbmcgd2l0aCA0LDIsMCwyLDAgZW50ZXJzIGEgbG9vcCBhZnRlciAyIHN0ZXBzOiZuYnNwOzxcL3A+XHJcblxyXG48cD4oNCwyLDAsMiwwKSAmcmFycjsgKDIsMiwyLDIsNCkgJnJhcnI7ICgwLDAsMCwyLDIpICZyYXJyOyAoMCwwLDIsMCwyKSAmcmFycjsgKDAsMiwyLDIsMikgJnJhcnI7ICgyLDAsMCwwLDIgJnJhcnI7PGJyIFwvPlxyXG4oMiwwLDAsMiwwKSAmcmFycjsgKDIsMCwyLDIsMikgJnJhcnI7ICgyLDIsMCwwLDApICZyYXJyOyAoMCwyLDAsMCwyKSAmcmFycjsgKDIsMiwwLDIsMikgJnJhcnI7ICgwLDIsMiwwLDAgJnJhcnI7PGJyIFwvPlxyXG4oMiwwLDIsMCwwKSAmcmFycjsgKDIsMiwyLDAsMikgJnJhcnI7ICgwLDAsMiwyLDApICZyYXJyOyAoMCwyLDAsMiwwKSAmcmFycjsgKDIsMiwyLDIsMCkgJnJhcnI7ICgwLDAsMCwyLDIpICZyYXJyOyAuLi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gbi10dXBsZSBvZiBpbnRlZ2Vycywgd3JpdGUgYSBwcm9ncmFtIHRvIGRlY2lkZSBpZiB0aGUgc2VxdWVuY2UgaXMgcmVhY2hpbmcgdG8gYSB6ZXJvcyB0dXBsZSBvciBhJm5ic3A7PGJyIFwvPlxyXG5wZXJpb2RpYyBsb29wLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgdGhlIGlucHV0IGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBuICgzICZsZTsgbiAmbGU7IDE1KSwgd2hpY2ggcmVwcmVzZW50cyB0aGUgc2l6ZSBvZiBhIHR1cGxlIGluIHRoZSBEdWNjaSBzZXF1ZW5jZXMuIEluIHRoZSBmb2xsb3dpbmcgbGluZSwgbiBpbnRlZ2VycyBhcmUgZ2l2ZW4gd2hpY2ggcmVwcmVzZW50cyB0aGUgbi10dXBsZSBvZiBpbnRlZ2Vycy4gVGhlIHJhbmdlIG9mIGludGVnZXJzIGFyZSBmcm9tIDAgdG8gMSwwMDAuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHN0ZXBzIG9mIGEgRHVjY2kgc2VxdWVuY2UgcmVhY2hpbmcgemVyb3MgdHVwbGUgb3IgbWFraW5nIGEgbG9vcCBkb2VzIG5vdCBleGNlZWQgMSwwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFByaW50IExPT1AgaWYgdGhlIER1Y2NpJm5ic3A7c2VxdWVuY2UgZmFsbHMgaW50byBhIHBlcmlvZGljIGxvb3AsIHByaW50IFpFUk8gaWYgdGhlIER1Y2NpIHNlcXVlbmNlIHJlYWNoZXMgdG8gYSB6ZXJvcyB0dXBsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2009 A번