Time Limit: 3s
Memory Limit: 128MB
세상에는 아직 답을 증명하지 못한 문제들이 많다. 여기 그런 문제들 중 하나를 소개해보려고 한다.
아래의 알고리즘을 생각해보자.
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가 가장 긴 것을 찾아보자!
각 줄마다 입력으로 2개의 수 p, q가 들어온다. p, q는 1,000,000 보다 작은 자연수이다. 입력은 EOF로 끝난다.
p와 q 사이에 있는 수중에 3n+1 알고리즘 계산과정에서 32bit signed-int 범위를 벗어나는 수는 등장하지 않는다고 가정해도 좋다.
각 줄마다 입력으로 들어온 p와 q, 그리고 p와 q 사이에 있는 수들의 cycle-length 중 최대값을 출력한다.
1 10 100 200 201 210 900 1000
1 10 20 100 200 125 201 210 89 900 1000 174
추가사항) 이 문제에는 소정의 낚시성분이 들어있습니다. 떡밥을 물어보세요 ^^
6월 5일 추가) p와 q 사이의 숫자에는 p랑 q도 있습니다.