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

두치수열은 모든 원소가 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이 되는지, 아니면 주기성을 가지는지를 판단하는 프로그램을 작성하라.

#1486 upload 4 done 3 how_to_reg 3

두치수열 timer 1s memory 64MB

#1486

두치수열 1s 64MB