차이의 반복

시간 제한1초메모리 제한128 MB

요약

네 양의 정수가 주어질 때, 이웃한 수의 차의 절댓값으로 계속 바꾸어 네 수가 모두 같아질 때까지 걸리는 단계 수를 센다.

문제

네 양의 정수 $a, b, c, d$ 가 주어지면, 원형으로 이웃한 두 수의 차의 절댓값을 취해 네 개의 새로운 수를 만든다.

$(\,|a-b|,\ |b-c|,\ |c-d|,\ |d-a|\,)$

이렇게 나온 네 수에 같은 연산을 다시 적용하고, 네 수가 모두 같아질 때까지 이 과정을 반복한다.

예를 들어 $1, 3, 5, 9$ 에서 시작하면 다음과 같다.

1  3  5  9
2  2  4  8   (1단계)
0  2  4  6   (2단계)
2  2  2  6   (3단계)
0  0  4  4   (4단계)
0  4  0  4   (5단계)
4  4  4  4   (6단계)

이 경우 수열은 6단계 만에 네 수가 모두 같아진다. $a, b, c, d$ 가 주어졌을 때, 수렴하기까지 몇 단계가 걸리는지 구하라. 처음부터 네 수가 모두 같다면 답은 $0$ 이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 네 정수 $a, b, c, d$ 가 주어진다( $1 \le a, b, c, d \le 2 \times 10^9$ ). 입력의 마지막 줄에는 0이 네 개 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스에 대해, 네 수가 모두 같아질 때까지 걸리는 단계 수를 출력한다.

네 정수가 모두 $2^n$ 보다 작다면, 수열은 $3n$ 단계 이내에 수렴한다.