Informatica Online Judge

  함수로 3n+1의 최대길이 구하기 [1279 / 04FF]

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


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

[JKJeong 2015]

Background

*주의사항 : 이 (함수 제출형) 문제는 함수 부분만 작성해서 제출해야 오류 없이 채점이 됩니다.
미리 작성되어있는 코드를 읽고 해석해서, 함수 부분만 작성해서 제출하면 됩니다.
작성한 함수의 테스트를 위해서는 제시된 코드를 복사해 사용하면 되고, 제출은 함수 부분만 하세요.

------

컴퓨터과학에서는 다양한 알고리즘을 이용한 여러 문제들이 있다. 그 중 3n+1이라고 하는 문제에 대해서 알아보자.

(1) input n
(2) print n
(3) if n = 1 then STOP
(4) if n is odd then n <-- 3n+1
(3) else n <-- n/2
(3) 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사이에서 가장 사이클 길이가 긴 것이 얼마인지 찾는 것이다.

[미리 작성된 프로그램]

#include <stdio.h>

int f(int);

void g(int &a, int &b) // reference를 이용한 전달
{
int t;
t = a;
a = b;
b = t;
}

int get_max(int a, int b)
{
return a > b ? a : b;
}

int main()
{
int a, b, ans = 0;
scanf("%d%d", &a, &b);
if( a > b )
g(a, b);
for(int i = a ; i <= b ; i++ )
ans = get_max( ans, f(i) );
printf("%d", ans);
return 0;
}

Input

[미리 입력된 프로그램의 입력]

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

Output

[미리 입력된 프로그램의 출력]

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]