점프 > 문제은행



문제은행

3338 : 점프

제한시간: 1Sec    메모리제한: 512mb
해결횟수: 14회    시도횟수: 71회   



개구리가 수직선 위의 0에서 출발해서 오른쪽(x좌표가 증가하는 방향)으로 점프들을 수행한 후 어떤 수 x > 0에 도착하려 한다. 

이 때, 점프 간격은 1로 부터 시작해서 항상 직전 점프한 간격의 2배로 증가해야 한다.

 

만일 점프간격을 2배씩 계속 증가시켜 마지막 목표 수 x를 지나칠 것 같으면, 

필요한 경우 언제든지 점프 간격을 다시 처음 상태인 간격 1로 되돌아 갈 수 있다.

이것을 재시작 이라고 부른다. 

 

예를 들어, 아래 <그림 1>과 같이 x=19에 도달 하기 위해서 2번 재시작을 수행해서

(1+2+4+8)+(1+2)+(1)=19와 같이 7번의 점프로 도착 할수 있다.

 

a337f11ba66a85c73925ae2bc035639d_1563095

개구리가 0에서 출발해서 어떤 양의 정수 N에 도달하기 위한 점프 횟수의 최솟값을 J(N)으로 나타내고 N의 점프넘버라고 부를 것이다.

예를 들어, <그림 1>을 보면 J(1)=1, J(3)=2, J(7)=3, J(15)=4, J(16)=5, J(18)=6, J(19)=7과 같음을 알 수 있다.

 

여러분은 어떤 특정 구간 [x,y]안의 수들의 점프넘버들 중 최댓값을 찾아서 출력한다. 

즉, 아래 조건을 만족하는 w를 찾아서 출력한다.

w = max{J(i)|x≤i≤​y}

 

 


표준 입력으로 다름 정보가 주어진다. 
첫 번째 줄에는 여러분에서 주어질 구간의 개수 T(1≤T≤2,000)가 주어진다.
이 후 T개의 줄에 대한 답을 구해야 할 구간을 나타내는 두 정수 x, y(1≤x≤y≤109)가 공백을 사이에 두고 주어진다.


표준 풀력으로 T개의 줄에 각각 하나의 정수를 출력한다.
각 줄에 출력되는 정수는 구간 [x,y]안의 수들의 점프넘버들 중 최댓값이다.
각 정수는 입력으로 주어지는 구간의 순서에 맞게 출력되어야 한다. 
즉, 첫번째 줄에 출력되는 정답은 첫 번째로 주어지는 구간에 대응되어야 한다.

채점 기준
제출된 프로그램은 여러 개의 테스트 케이스로 평가되며, 
맞은 테스트 케이스에 대해서 해당 테스트 케이스에 배정된 점수를 받는다. 
모든 테스트 케이스를 맞았을 시 100점을 받는다.

각 테스트 케이스에 대한 배점 정보와, 제약 조건은 다음과 같다:
  • 그룸 1: 총 10점 상당의 테스트 케이스로 구성되어 있다. 각각의 1≤x≤y≤20을 만족한다.
  • 그룸 2: 총 16점 상당의 테스트 케이스로 구성되어 있다. 각각의 1≤x≤y≤2,000을 만족한다.
  • 그룸 3: 총 8점 상당의 테스트 케이스로 구성되어 있다. 각각의 1≤x≤y≤1,000,000, y-x≤2,000을 만족한다.
  • 그룸 4: 총 21점 상당의 테스트 케이스로 구성되어 있다. 각각의 1≤x≤y≤4,000,000을 만족한다.
  • 그룸 5: 총 45점 상당의 테스트 케이스로 구성되어 있다. 추가적인 제약 조건이 없다.

  • [Copy]
    3
    1 4
    7 7
    12 16
    [Copy]
    3
    3
    7






    HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
    경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
    Copyright@2010-2015 jungol. All right reserved.