切換
舊版
前往
大廳
主題

ZeroJudge - e514: 01594 - Ducci Sequence 解題心得

Not In My Back Yard | 2019-11-07 12:05:15 | 巴幣 0 | 人氣 217

題目連結:


題目大意:
給定一正整數 T ,代表接下來有 T 筆測試資料。每筆測試資料的第一列給定一正整數 n (3 ≦ n ≦ 15),代表一個多元組(Tuple)的長度。

接著的一列給定 n 個非負整數 ai(值不超過 1000),代表此 n 元組的內容。因此此 n 元組為 ( a1, a2, ……, an )。

而一個 n 元組的「下一個」序列為
( |a1 - a2|, |a2 - a3|, ……, |an - a1| )
例如 (8, 11, 2, 7) 的下一個序列為 (3, 9,  5, 1) 。

而這種序列稱為「Ducci Sequence」,其最終序列不是達到零元組(元組內容值皆為 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, 1) → (2, 1, 3) → (1, 2, 1) → (1, 1, 0) → (0, 1, 1) → (1, 0, 1) → (1, 1, 0) → ……

請判斷給定的 n 元組最終是否會循環,還是抵達零元組?如果會循環,請輸出「LOOP」;反之,輸出「ZERO」。(保證抵達零元組或是開始循環時所需的迭代步驟不超過 1000 步)



範例輸入:
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


解題思維:
因為迭代不會超過 1000 ,所以就直接迭代 1000 次即可(當然,也可以判斷有沒有重複。有重複出現的項次就跳出)。如果中途碰到了零元組就跳出。

最後判斷有沒有跑滿 1000 即可判斷是「LOOP」,還是「ZERO」x了。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作