1271 - 3n + 1 문제

Time Limit: 3s Memory Limit: 128MB

Submissions: 478 Solved: 110
Description

세상에는 아직 답을 증명하지 못한 문제들이 많다. 여기 그런 문제들 중 하나를 소개해보려고 한다.

아래의 알고리즘을 생각해보자.

1. input n.

2. if n = 1 then STOP.

3. if n is odd, n ← 3n+1

4. if n is even, n ← n/2

5. GOTO 2

 

만약 입력으로 22가 들어왔다면, n은 순서대로

22 → 11 → 34 → 17 

→ 52 → 26 → 13 → 40

→ 20 → 10 → 5 → 16

→ 8 → 4 → 2 → 1

이 된다.

 

모든 자연수에 대해 위의 단순한 알고리즘이 항상 종료될 것이라는 추측은 있지만, 종료된다는 것도 그렇지 않다는 것도 증명된 바가 없다. 단, 적어도 0 < n < 1,000,000 인 경우에는 항상 종료됨이 보장되있다.

 

주어진 n에 대해, 이 n이 1이 될 때 까지 등장한 숫자들의 개수를 구할 수 있다. (1을 포함해서) 우리는 이를 cycle-length라고 부를 것이다. 위의 예제에서, 22의 cycle-length는 16이다.

입력으로 두 수 p, q가 들어왔을 때, p와 q 사이의 수 중 cycle-length가 가장 긴 것을 찾아보자!

Input

각 줄마다 입력으로 2개의 수 p, q가 들어온다. p, q는 1,000,000 보다 작은 자연수이다. 입력은 EOF로 끝난다.

p와 q 사이에 있는 수중에 3n+1 알고리즘 계산과정에서 32bit signed-int 범위를 벗어나는 수는 등장하지 않는다고 가정해도 좋다.

Output

각 줄마다 입력으로 들어온 p와 q, 그리고 p와 q 사이에 있는 수들의 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
Hint

추가사항) 이 문제에는 소정의 낚시성분이 들어있습니다. 떡밥을 물어보세요 ^^

 

6월 5일 추가) p와 q 사이의 숫자에는 p랑 q도 있습니다.