루미 알고리즘

#1098실버보물찾기보물찾기

KOI 2024 2차코딩초등부 1번출제 정보올림피아드위원회이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

보물찾기

원제: 보물찾기

문제

당신은 친구인 다빈과 함께 아래와 같이 무한히 긴 수직선 위에서 보물찾기 놀이를 하고 있다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

먼저 당신은 수직선에 있는 서로 다른 두 위치 LL, RR에 보물 두 개를 숨긴다. (L<RL < R) 아래는 숨긴 두 보물의 위치가 L=−2L = -2, R=3R = 3인 경우의 예시이다. 주황색으로 표시된 두 개의 칸에 보물이 숨겨져 있다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

당신이 보물 두 개를 숨긴 다음, 다빈이 보물을 찾기 시작한다. 다빈은 당신이 정한 시작 위치 SS에서 시작해, 아래 단계들을 순서대로 수행하며 보물을 찾을 것이다. 시작 위치 SS는 항상 두 보물의 위치 LL과 RR 사이에 있다. (L<S<RL < S < R) 두 보물 중 하나의 보물을 찾으면 보물찾기 놀이가 끝난다.

  1. 위치 SS를 조사한다.
  2. 오른쪽으로 11칸 이동해, 위치 S+1S + 1를 조사한다.
  3. 왼쪽으로 22칸 이동해, 위치 S+1−2S + 1 - 2를 조사한다.
  4. 오른쪽으로 33칸 이동해, 위치 S+1−2+3S + 1 - 2 + 3를 조사한다.
  5. 왼쪽으로 44칸 이동해, 위치 S+1−2+3−4S + 1 - 2 + 3 - 4를 조사한다.
  6. 오른쪽으로 55칸 이동해, 위치 S+1−2+3−4+5S + 1 - 2 + 3 - 4 + 5를 조사한다.
  7. ...

즉, xx번째 단계에서는, xx가 짝수라면 오른쪽으로 x−1x - 1칸 이동하고 xx가 홀수라면 왼쪽으로 x−1x - 1칸 이동해서 도착한 위치를 조사한다. 만약, 어떤 단계에서 조사한 칸에 보물이 있으면 보물찾기 놀이가 끝난다. 아래 그림은 L=−2L = -2, R=3R = 3이고 다빈의 시작 위치 S=0S = 0인 경우의 보물찾기 놀이의 과정이다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

5번째 단계에서 조사한 위치 −2-2에 보물이 있으므로, 5번째 단계에서 보물찾기 놀이가 끝난다.

당신이 정하는 세 변수 LL, RR, SS의 값에 따라서, 보물찾기 놀이가 끝나는 단계가 달라진다. 따라서, 당신은 세 변수 값의 조합을 여러 가지 시도해 보려 한다.

각 경우에 대해, 두 보물의 위치 LL, RR과 다빈이 시작하는 위치 SS가 주어졌을 때, 몇 번째 단계에서 보물찾기 놀이가 끝나는지 구하여라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤T≤10 0001 \le T \le 10\,000
  • −100 000 000≤L<S<R≤100 000 000-100\,000\,000 \le L < S < R \le 100\,000\,000

부분문제

  1. (8점) T=1T = 1, R=1R = 1, S=0S = 0
  2. (9점) T=1T = 1, L=−1L = -1, S=0S = 0
  3. (15점) −1 000≤L≤−1-1\,000 \le L \le -1, 1≤R≤1 0001 \le R \le 1\,000, S=0S = 0
  4. (16점) −1 000≤L<S<R≤1 000-1\,000 \le L < S < R \le 1\,000
  5. (52점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 당신이 시도해 볼 경우의 수 TT가 주어진다. 이후 TT개의 줄에, 각 경우에 대해 세 변수 LL, RR, SS의 값이 공백으로 구분되어 주어진다.

출력 형식

TT개의 줄에 걸쳐, 각 경우에 몇 번째 단계에서 보물찾기 놀이가 끝나는지 출력한다.

예제

예제 1

입력
2
-2 3 0
4 8 6
출력
5
4

첫 번째 경우 (L=−2L = -2, R=3R = 3, S=0S = 0)는 위의 그림에 설명되어 있다.

두 번째 경우 (L=4L = 4, R=8R = 8, S=6S = 6)에서 다빈은 아래와 같은 과정으로 보물을 찾게 된다.

  1. 위치 66을 조사한다.
  2. 오른쪽으로 11칸 이동해, 위치 6+1=76 + 1 = 7을 조사한다.
  3. 왼쪽으로 22칸 이동해, 위치 7−2=57 - 2 = 5를 조사한다.
  4. 오른쪽으로 33칸 이동해, 위치 5+3=85 + 3 = 8을 조사한다.

4번째 단계에서 조사하는 위치 88에는 보물이 있으므로, 4번째 단계에서 보물찾기 놀이가 끝난다.

예제 2

입력
9
-1 1 0
-2 1 0
-3 1 0
-1 2 0
-2 2 0
-3 2 0
-1 3 0
-2 3 0
-3 3 0
출력
2
2
2
3
4
4
3
5
6

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.