당신은 친구인 다빈과 함께 아래와 같이 무한히 긴 수직선 위에서 보물찾기 놀이를 하고 있다
먼저 당신은 수직선에 있는 서로 다른 두 위치 \(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\)인 경우의 보물찾기 놀이의 과정이다.
  5번째 단계에서 조사한 위치 −2에 보물이 있으므로, 5번째 단계에서 보물찾기 놀이가 끝난다.
  당신이 정하는 세 변수 \(L, R, S\)의 값에 따라서, 보물찾기 놀이가 끝나는 단계가 달라진다. 따라서, 당신은 세 변수 값의 조합을 여러 가지 시도해 보려 한다.
  각 경우에 대해, 두 보물의 위치 \(L, R\)과 다빈이 시작하는 위치 \(S\)가 주어졌을 때, 몇 번째 단계에서 보물찾기 놀이가 끝나는지 구하여라. 

제약 조건
• 주어지는 모든 수는 정수이다.
• \(1 \le T \le 10 000\)
• \(−100 000 000 \le L < S < R \le 100 000 000\)

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

첫 번째 줄에 당신이 시도해 볼 경우의 수 \(T\)가 주어진다. 이후 \(T\)개의 줄에, 각 경우에 대해 세 변수 \(L, R, S\)의 값이 공백으로 구분되어 주어진다.

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

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2024KOI2차