e514: 01594 - Ducci Sequence
Tags : 模擬
Accepted rate : 105人/105人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-27 13:49

Content

Ducci sequence是整數n元組序列。
規則是給定一個n元組序列 (a1, a2, ..., an),該序列中的下一個n元組序列是通過獲取相鄰整數的絕對差形成的:

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

Ducci sequence到最後會達到零元組或者陷入週期性循環。
例如:

(8, 11, 2, 7)開頭的4元組序列,需要5個步驟達到零元組:

(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)開頭的5元組序列,在第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元組序列,請你判斷該序列是達到零元組還是進入週期性循環。

Input

輸入第一行為一個整數T,代表以下包含T個Case。
每個Case第一行有一個整數n (3 ≤ n ≤ 15),該行表示Ducci sequences中元組的大小。
接下來一行有n個整數ai (0 ≤ ai ≤ 1000)。
你可以假設Ducci sequences達到零元組或進入週期性循環的最大步數不超過1000。

Output

每個Case輸出一行
如果Ducci sequence進入週期性循環
輸出"LOOP"
如果Ducci sequence達到零元組
輸出"ZERO"

Sample Input #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
Sample Output #1
ZERO
LOOP
ZERO
LOOP
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1K
Hint :
Tags:
模擬
出處:
UVA [管理者: ig99lp33lp33(위즈원) ]


ID User Problem Subject Hit Post Date
30487 jojojo22845@...(lu) e514
想法
55 2022-05-24 23:55