보물찾기

2024년도한국정보올림피아드2차대회문제
보물찾기
당신은친구인다빈과함께아래와같이무한히긴수직선위에서보물찾기놀이를하고있다.
먼저당신은수직선에있는서로다른두위치\(L\), \(R\)에보물두개를숨긴다. (\(L\) < \(R\)) 아래는숨긴두
보물의위치가\(L\) = −2, \(R\) = 3인경우의예시이다. 주황색으로표시된두개의칸에보물이숨겨져있다.
당신이보물두개를숨긴다음, 다빈이보물을찾기시작한다. 다빈은당신이정한시작위치\(S\)에서시작해,
아래단계들을순서대로수행하며보물을찾을것이다. 시작위치\(S\)는항상두보물의위치\(L\)과\(R\) 사이에
있다. (\(L\) < \(S\) < \(R\)) 두보물중하나의보물을찾으면보물찾기놀이가끝난다.
1. 위치\(S\)를조사한다.
2. 오른쪽으로1칸이동해, 위치\(S\) + 1를조사한다.
3. 왼쪽으로2칸이동해, 위치\(S\) + 1 −2를조사한다.
4. 오른쪽으로3칸이동해, 위치\(S\) + 1 −2 + 3를조사한다.
5. 왼쪽으로4칸이동해, 위치\(S\) + 1 −2 + 3 −4를조사한다.
6. 오른쪽으로5칸이동해, 위치\(S\) + 1 −2 + 3 −4 + 5를조사한다.
7. . . .
즉, \(x\)번째단계에서는, \(x\)가짝수라면오른쪽으로\(x\) −1칸이동하고\(x\)가홀수라면왼쪽으로\(x\) −1칸이동해
서도착한위치를조사한다. 만약, 어떤단계에서조사한칸에보물이있으면보물찾기놀이가끝난다. 아래
그림은\(L\) = −2, \(R\) = 3이고다빈의시작위치\(S\) = 0인경우의보물찾기놀이의과정이다.
2024년도한국정보올림피아드2차대회문제
5번째단계에서조사한위치−2에보물이있으므로, 5번째단계에서보물찾기놀이가끝난다.
당신이정하는세변수\(L\), \(R\), \(S\)의값에따라서, 보물찾기놀이가끝나는단계가달라진다. 따라서, 당신은
세변수값의조합을여러가지시도해보려한다.
각경우에대해, 두보물의위치\(L\), \(R\)과다빈이시작하는위치\(S\)가주어졌을때, 몇번째단계에서보물찾기
놀이가끝나는지구하여라.
제약조건
• 주어지는모든수는정수이다.
• 1 ≤\(T\) ≤10 000
• −100 000 000 ≤\(L\) < \(S\) < \(R\) ≤100 000 000

부분문제
1. (8점) \(T\) = 1, \(R\) = 1, \(S\) = 0
2. (9점) \(T\) = 1, \(L\) = −1, \(S\) = 0
3. (15점) −1 000 ≤\(L\) ≤−1, 1 ≤\(R\) ≤1 000, \(S\) = 0
4. (16점) −1 000 ≤\(L\) < \(S\) < \(R\) ≤1 000
5. (52점) 추가제약조건없음.
입력형식
첫번째줄에당신이시도해볼경우의수\(T\)가주어진다. 이후\(T\)개의줄에, 각경우에대해세변수\(L\), \(R\),
\(S\)의값이공백으로구분되어주어진다.
출력형식
\(T\)개의줄에걸쳐, 각경우에몇번째단계에서보물찾기놀이가끝나는지출력한다.
예제1
표준입력(stdin)
표준출력(stdout)
2
-2 3 0
4 8 6
5
4
첫번째경우(\(L\) = −2, \(R\) = 3, \(S\) = 0)는위의그림에설명되어있다.
두번째경우(\(L\) = 4, \(R\) = 8, \(S\) = 6)에서다빈은아래와같은과정으로보물을찾게된다.
1. 위치6을조사한다.
2. 오른쪽으로1칸이동해, 위치6 + 1 = 7을조사한다.
3. 왼쪽으로2칸이동해, 위치7 −2 = 5를조사한다.
4. 오른쪽으로3칸이동해, 위치5 + 3 = 8을조사한다.
4번째단계에서조사하는위치8에는보물이있으므로, 4번째단계에서보물찾기놀이가끝난다.
2024년도한국정보올림피아드2차대회문제
예제2
표준입력(stdin)
표준출력(stdout)
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차 대회 > 정보올림피아드위원회