어느 역에 A 노선과 B 노선의 열차가 들어온다.
A 노선의 시각표에는 열차 n대가 닿는 시각 a_1 < a_2 < … < a_n이, B 노선의 시각표에는 열차 m대가 닿는 시각 b_1 < b_2 < … < b_m이 초 단위로 적혀 있다.
질문 q개가 주어진다. 질문은 서로 상관이 없다.
질문 "k d"는 B 노선의 모든 열차가 시각표보다 d초씩 늦게 닿고 A 노선은 시각표대로 닿는 날에, 두 노선을 통틀어 k번째로 닿는 열차를 묻는다.
두 열차가 같은 시각에 닿으면 A 노선 열차가 먼저 닿은 것으로 친다.
질문마다 그 열차의 노선(A 또는 B), 그 노선의 시각표에서 몇 번째 열차인지, 그날 실제로 닿는 시각을 빈칸 하나로 띄워 한 줄에 출력하라.
예시 1에서 d가 5이면 B 노선 열차는 10, 20, 30, 45초에 닿는다. 그래서 닿는 차례는 A의 1번(10), B의 1번(10), A의 2번(20), B의 2번(20), A의 3번(30), B의 3번(30), B의 4번(45)이다.
입력
첫 줄에 n, m, q가 빈칸 하나로 띄워 주어진다. 둘째 줄에 a_1, …, a_n이, 셋째 줄에 b_1, …, b_m이 빈칸 하나로 띄워 주어진다. 다음 q줄에 k와 d가 빈칸 하나로 띄워 주어진다. 1 ≤ n, m ≤ 9,000, 1 ≤ q ≤ 9,000, 0 ≤ a_i, b_i ≤ 2 × 10^9, 1 ≤ k ≤ n + m, 0 ≤ d ≤ 2 × 10^9(모두 정수이고, 쉼표 없이 숫자만 주어진다)
출력
질문마다 한 줄에 노선(A 또는 B), 그 노선에서 몇 번째 열차인지, 그날 실제로 닿는 시각
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
먼저 닿는 k대 가운데 A 노선이 i대라면 B 노선은 k-i대예요. 이 i를 이분 탐색으로 찾아요. A의 a[mid](0부터 셈)가 앞의 k대에 들려면 그보다 먼저 닿는 B 열차가 k-mid-1대 이하여야 하고, 이는 b[k - mid - 1] + d >= a[mid]와 같아요. mid가 커질수록 이 조건은 참에서 거짓으로 한 번만 바뀌어요. 참이면 lo = mid + 1, 거짓이면 hi = mid로 좁혀 가면 14번쯤 만에 i가 정해져요. k번째 열차는 A의 i번째와 B의 k-i번째 가운데 늦게 닿는 쪽이에요. 가운데는 Python (lo + hi) // 2, Java·C#·C·C++ (lo + hi) / 2, JavaScript·TypeScript Math.floor((lo + hi) / 2), 크레이콘 수학.몫(lo + hi, 2)로 구해요. Python bisect나 C++ std::lower_bound는 목록 하나에서 값 하나를 찾는 도구라서, 두 목록을 함께 보는 이 조건에는 그대로 쓸 수 없어 반복을 직접 썼어요. 함정 하나: 질문마다 두 시각표를 앞에서부터 k대까지 하나씩 세면 가장 큰 입력에서 약 1억 6천만 번을 세요. d가 질문마다 달라서 한 번 합쳐 둔 차례를 다시 쓸 수도 없어요. 이렇게 짠 Python 풀이는 시간 안에 끝나지 않았어요. 솔직히 말하면 같은 방식의 C 풀이는 이 컴퓨터에서 0.4초 안에 끝났어요. 이분 탐색이 꼭 필요한 것은 느린 언어에서예요. 함정 둘: 같은 시각이면 A가 먼저예요. 그래서 조건과 마지막 비교가 >=여야 해요. 둘을 >로 쓰면 B가 먼저인 것으로 세어져, 예시 1의 둘째 질문 "2 5"는 B 1 10이 아니라 A 1 10이, 셋째 질문은 A 2 20이 아니라 B 2 20이 나와요. 함정 셋: i의 범위는 0부터 n까지가 아니라 max(0, k - m)부터 min(k, n)까지예요. 범위를 0부터 n까지로 잡으면 k - mid - 1이 음수가 되거나 m 이상이 돼요. Python은 음수 번호를 뒤에서부터 센 자리로 읽기 때문에 예시 1의 첫 질문에서 조용히 A 2 20을 출력하고(답은 B 1 5), 다섯째 질문 "7 5"에서는 b[5]를 읽다가 IndexError로 멈춰요. Java·C#은 두 경우 모두 예외로 멈추고, C·C++은 무슨 일이 생길지 정해져 있지 않아요. 함정 넷: 출력하는 시각은 시각표의 시각이 아니라 그날 실제로 닿는 시각이에요. B 노선이면 d를 더해야 해요. 더하지 않으면 예시 1의 둘째 질문이 B 1 10이 아니라 B 1 5가 돼요. 함정 다섯: 시각도 d도 2 × 10^9까지라 저마다는 32비트 int에 들어가지만, 더하면 4 × 10^9까지 커져 넘쳐요. Java·C#·C·C++은 시각과 d를 long/long long에 담아야 해요. Java에서 int에 담으면 예시 2의 둘째 질문에서 4000000000이 -294967296으로 바뀌어 B 2 4000000000이 아니라 A 1 2000000000이 나와요. Python의 정수는 크기 제한이 없고, JavaScript·TypeScript·크레이콘의 수는 2^53까지 정확해서 그대로 맞아요.
Pythonmain.py · 33 줄
import sysdef main(): data = sys.stdin.buffer.read().split() n, m, q = int(data[0]), int(data[1]), int(data[2]) a = [int(x) for x in data[3:3 + n]] b = [int(x) for x in data[3 + n:3 + n + m]] out = [] pos = 3 + n + m for _ in range(q): k, d = int(data[pos]), int(data[pos + 1]) pos += 2 # 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = max(0, k - m) hi = min(k, n) while lo < hi: mid = (lo + hi) // 2 # A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if b[k - mid - 1] + d >= a[mid]: lo = mid + 1 else: hi = mid i, j = lo, k - lo # k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if i == 0 or (j > 0 and b[j - 1] + d >= a[i - 1]): out.append("B %d %d" % (j, b[j - 1] + d)) else: out.append("A %d %d" % (i, a[i - 1])) print("\n".join(out))main()
JavaScriptmain.js · 27 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a = data.slice(3, 3 + n);const b = data.slice(3 + n, 3 + n + m);const out = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
TypeScriptmain.ts · 28 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a: number[] = data.slice(3, 3 + n);const b: number[] = data.slice(3 + n, 3 + n + m);const out: string[] = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
JavaMain.java · 42 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] a = new long[n]; long[] b = new long[m]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < m; i++) b[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int x = 0; x < q; x++) { st = new StringTokenizer(in.readLine()); int k = Integer.parseInt(st.nextToken()); long d = Long.parseLong(st.nextToken()); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.max(0, k - m); int hi = Math.min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) { out.append("B ").append(j).append(' ').append(b[j - 1] + d).append('\n'); } else { out.append("A ").append(i).append(' ').append(a[i - 1]).append('\n'); } } System.out.print(out); }}
C#Main.cs · 38 줄
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), m = int.Parse(p[1]), q = int.Parse(p[2]); long[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int x = 0; x < q; x++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int k = int.Parse(p[0]); long d = long.Parse(p[1]); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.Max(0, k - m); int hi = Math.Min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) sb.Append("B ").Append(j).Append(' ').Append(b[j - 1] + d).Append('\n'); else sb.Append("A ").Append(i).Append(' ').Append(a[i - 1]).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 34 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<long long> a(n), b(m); for (auto& v : a) cin >> v; for (auto& v : b) cin >> v; while (q--) { int k; long long d; cin >> k >> d; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = max(0, k - m); int hi = min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) cout << "B " << j << ' ' << b[j - 1] + d << '\n'; else cout << "A " << i << ' ' << a[i - 1] << '\n'; } return 0;}
Cmain.c · 30 줄
#include <stdio.h>static long long a[9000], b[9000];int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &a[i]) != 1) return 0; for (int i = 0; i < m; i++) if (scanf("%lld", &b[i]) != 1) return 0; for (int x = 0; x < q; x++) { int k; long long d; if (scanf("%d %lld", &k, &d) != 2) return 0; /* 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. */ int lo = k - m > 0 ? k - m : 0; int hi = k < n ? k : n; while (lo < hi) { int mid = (lo + hi) / 2; /* A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 */ if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; /* k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 */ if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) printf("B %d %lld\n", j, b[j - 1] + d); else printf("A %d %lld\n", i, a[i - 1]); } return 0;}
Craykonmain.cray · 40 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];a = 콘솔.수들읽기();b = 콘솔.수들읽기();반복 (x = 0; x < q; x++){ 줄 = 콘솔.수들읽기(); k = 줄[0]; d = 줄[1]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = 수학.큰수(0, k - m); hi = 수학.작은수(k, n); 동안 (lo < hi) { mid = 수학.몫(lo + hi, 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 만약 (b[k - mid - 1] + d >= a[mid]) { lo = mid + 1; } 아니면 { hi = mid; } } i = lo; j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 만약 (i == 0 || j > 0 && b[j - 1] + d >= a[i - 1]) { 콘솔.쓰기("B " + j + " " + (b[j - 1] + d)); } 아니면 { 콘솔.쓰기("A " + i + " " + a[i - 1]); }}