루미 알고리즘

#1121플래티넘로봇로봇

KOI 2025 2차코딩중등부 3번출제 오주원이 문제가 어렵다면 — 배우는 순서 보기

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

로봇

원제: 로봇

문제

수직선 위 서로 다른 위치에 NN개의 점프대가 설치되어 있다. ii번 점프대는 고정된 위치 XiX_i와 초기 점프 파워 PiP_i를 가진다. 당신은 이 수직선 위의 어떤 위치에 로봇을 놓을 것이다.

로봇은 다음과 같은 규칙에 따라 움직인다:

  • 로봇이 위치한 지점에 점프대가 없을 경우, 로봇은 왼쪽으로 11만큼 이동한다. 이 과정에서 11의 시간이 소요된다.
  • 로봇이 위치한 지점에 점프대가 있을 경우, 로봇은 즉시 점프대를 작동시켜 오른쪽으로 점프대의 파워만큼 이동한다. 점프 후 점프대의 파워는 기존의 두 배로 증가한다. 이 과정에서 11의 시간이 소요된다.

예를 들어, N=2N = 2개의 점프대가 다음과 같이 설치되어 있다고 하자.

점프대 번호위치 XiX_i초기 파워 PiP_i
122
253

로봇이 초기 위치 S=3S = 3에서 출발하여 T=7T = 7만큼의 시간 동안 이동하는 과정은 다음과 같다.

시간 (TT)로봇 위치설명점프대 상태
03초기 위치에서 시작한다.P1=2,P2=3P_1 = 2, P_2 = 3
12점프대가 없으므로 왼쪽으로 1칸 이동했다.P1=2,P2=3P_1 = 2, P_2 = 3
24위치 2에 있는 1번 점프대를 작동시켜 오른쪽으로 2만큼 점프했다.P1=4,P2=3P_1 = 4, P_2 = 3
33점프대가 없으므로 왼쪽으로 1칸 이동했다.P1=4,P2=3P_1 = 4, P_2 = 3
42점프대가 없으므로 왼쪽으로 1칸 이동했다.P1=4,P2=3P_1 = 4, P_2 = 3
56위치 2에 있는 1번 점프대를 작동시켜 오른쪽으로 4만큼 점프했다.P1=8,P2=3P_1 = 8, P_2 = 3
65점프대가 없으므로 왼쪽으로 1칸 이동했다.P1=8,P2=3P_1 = 8, P_2 = 3
78위치 5에 있는 2번 점프대를 작동시켜 오른쪽으로 3만큼 점프했다.P1=8,P2=6P_1 = 8, P_2 = 6

QQ개의 정수 쌍 (Sj,Tj)(S_j, T_j)(1≤j≤Q1 \le j \le Q)이 주어진다. 각 쌍에 대해, 로봇이 위치 SjS_j에서 출발하여 정확히 TjT_j의 시간이 지난 후 도달하게 되는 위치를 구하는 프로그램을 작성하라.

로봇의 위치는 서로 독립적으로 계산되어야 하며, 항상 점프대의 초기 상태에서 시작한다. 즉, 각 경우마다 로봇은 수직선 위에 단 하나 존재하며, 점프대의 파워는 입력에서 주어진 초깃값으로부터 다시 시작한다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤300 0001 \le N \le 300\,000
  • −1017≤X1<X2<...<XN≤1017-10^{17} \le X_1 < X_2 < ... < X_N \le 10^{17}
  • 1≤Pi≤1017(1≤i≤N)1 \le P_i \le 10^{17} (1 \le i \le N)
  • 1≤Q≤300 0001 \le Q \le 300\,000
  • −1017≤Sj≤1017,1≤Tj≤1017(1≤j≤Q)-10^{17} \le S_j \le 10^{17}, 1 \le T_j \le 10^{17} (1 \le j \le Q)

부분문제

  1. (5점) N=1N = 1
  2. (11점) N=2N = 2
  3. (6점) N,Q≤300N, Q \le 300, 1≤i≤N1 \le i \le N인 모든 ii에 대하여 ∣Xi∣,Pi≤300|X_i|, P_i \le 300, 1≤j≤Q1 \le j \le Q인 모든 jj에 대하여 ∣Sj∣,Tj≤300|S_j|, T_j \le 300
  4. (7점) N,Q≤3 000N, Q \le 3\,000, 1≤i≤N1 \le i \le N인 모든 ii에 대하여 ∣Xi∣,Pi≤3 000|X_i|, P_i \le 3\,000, 1≤j≤Q1 \le j \le Q인 모든 jj에 대하여 ∣Sj∣,Tj≤3 000|S_j|, T_j \le 3\,000
  5. (12점) N,Q≤9 000N, Q \le 9\,000
  6. (23점) N≤9 000N \le 9\,000
  7. (36점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 NN이 주어진다.

다음 NN개의 줄에 걸쳐 NN개의 정수 쌍이 주어진다. 이 중 ii(1≤i≤N1 \le i \le N)번째 줄에는 XiX_i와 PiP_i가 공백을 사이에 두고 주어진다.

다음 줄에는 QQ가 주어진다.

다음 QQ개의 줄에 걸쳐 QQ개의 정수 쌍이 주어진다. 이 중 jj(1≤j≤Q1 \le j \le Q)번째 줄에는 SjS_j와 TjT_j가 공백을 사이에 두고 주어진다.

출력 형식

QQ개의 줄을 출력한다. 이 중 jj(1≤j≤Q1 \le j \le Q)번째 줄에는 로봇이 SjS_j에서 출발하여 정확히 TjT_j의 시간이 지난 후 도달하는 위치를 출력한다.

예제

예제 1

입력
2
2 2
5 3
7
3 1
3 2
3 3
3 4
3 5
3 6
3 7
출력
2
4
3
2
6
5
8

예제 2

입력
3
-3 3
2 2
11 6
4
1 6
6 12
11 3
9 4
출력
-1
2
15
5

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.