Informatica Online Judge

  3n+1 (기초) (NTTP) [0125 / 007D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 1657   Total Tried : 1996


The Champion of this Problem (C++) : gs18017 - ms / 275byte
My Best Submission (C++) : N/A

[]

Background

컴퓨터과학에서는 다양한 알고리즘을 이용한 여러 문제들이 있다. 그 중 3n+1이라고 하는 문제에 대해서 알아보자.
(문제가 이해가 되지 않는 다면? 콜라츠 추측, 우박수에 대해서 찾아보자.)
(1) input n
(2) print n
(3) if n = 1 then STOP //n의 값이 1이면 종료
(4) if n is odd then n <-- 3n+1 //홀 수 이면 3*n+1 로 값을 바꿈
(5) else n <-- n/2 //짝 수 이면 n/2 로 값을 바꿈
(6) goto (2)

만약 n이 22라면 위 알고리즘은 다음과 같은 값을 출력한다.
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
어떤 수 n에 대해서 나타나는 수열의 길이를 사이클 길이라고 한다.
위와 같이 입력이 22인 경우 총 16개의 길이를 가지는 수열을 출력한다. 따라서 22의 사이클길이는 16이다.
이 알고리즘은 우리가 다루는 대부분의 수의 범위 내에서는 일정한 출력 후에 종료되지만 아직 모든 입력값에 대해서 성립함이 증명되지는 않았다.
이 문제는 주어진 입력 a, b사이에서 가장 사이클 길이가 긴 것이 얼마인지 찾는 것이다.

Input

두 정수 a, b가 공백으로 구분되어 주어진다. N(1≤ a, b ≤100,000)

Output

a에서 b사이에 있는 정수들로 만들어지는 사이클 가운데, 가장 긴 사이클 길이를 출력한다.
[a, b], a와 b도 포함된다.

IO Example

입출력예시1>
입력
1 10

출력
20


입출력예시2>
입력
201 210

출력
89

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]