The 3n + 1 problem

invalid-file

다음과 같은 수열을 생성하는 알고리즘을 생각해보자. 정수 n부터 시작한다. n이 짝수이면 1을 곱하고, 홀수이면 3을 곱하고 1을 더한다. 이 과정을 n=1이 될때까지 반복한다. 예를 들어, n=22이면 다음과 같은 수열을 생성한다.

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
이 알고리즘은 모든 정수에서 n=1이 되어 종료될 것으로 추측된다.(아직 증명되지는 않았다.)

입력 n에 대해서 n의 cycle-length는 1을 포함하여 생성된 수의 개수이다. 위의 예에서 22의 cycle-length는 16이다. 두 수 i와 j가 주어지면 i와 j사이의 모든 수의 cycle-length 중 가장 큰 값을 구한다.

입력
한 줄에 i와 j가 연속하여 입력된다. i와 j는 1,000,000보다 작고 0보다 크다.

출력
입력된 정수쌍 i, j (입력된 순서대로) 그리고 가장 큰 cycle-length를 출력한다. 이 세 숫자는 스페이스 한칸으로 구분한다.

Sample Input
1 10
100 200
201 210
900 1000

Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

참고사항 (제가 어려움을 겪었던 사항입니다)

1. 입력은 한번만 받고 끝나는 것이 아니라 계속 입력 받도록 합니다.

2. 계속 입력을 받을 때 최대 cycle length를 초기화 해줘야 함에 주의합니다.

3. 큰 수가 먼저 입력되는 경우를 고려해야 합니다. 작은 수 먼저 입력으로 들어오리란 보장은 없습니다. 입력 예에 한정해서 생각하면 안되죠.

4. 마지막으로 수열은 int형의 범위를 넘어설 수 있다는 것을 고려해야 합니다. 수열을 int형 범위로 제한하면 1 999999 결과로 1 999999 476 출력됩니다. 그러나 unsigned int형 범위로 제한하면 1 999999 결과로 1 999999 525 출력됩니다. 이러한 현상은 원인은 다음과 같습니다. 최대 값이 나오는 수는 837799인데 int형으로 하면 59가 나옵니다. 어느 순간 값이 2974984576이 되는데 이것이 int형(32비트)의 경우 범위를 넘어서서 -1319982720 이 되버리는 결과를 초래합니다. 그래서 반드시 unsigned int로 해주어야 제대로 된 값이 나옵니다. 어이 없는건 submit에는 문제가 없다는 겁니다-_-;;