시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB35422019364.983%

문제

서강대에서 이용하기 편한 전철 역은 2호선 신촌역, 6호선 대흥역, 경의중앙선 서강대역이 있다.

이 전철역들은 순서대로 $(X_1, Y_1), (X_2, Y_2), (X_3, Y_3)$에 위치한다.

$2^{025}$년, 과학 기술의 발전으로 각 노선의 배차간격이 일정해진 시기, 기숙사에 들어가지 못한 152학번 민수는 전철을 이용해 통학한다.

어느 날 민수는 이런 의문을 가졌다:

현재 자신의 위치가 $(X, Y)$이고, 각 역의 배차간격은 신촌역은 $T_1$분, 대흥역은 $T_2$분, 서강대역은 $T_3$분이라 하자.

$(X_i, Y_i)$에 위치한 전철역에 도착하는 데 $|X - X_i| + |Y - Y_i|$분이 걸릴 때, 가장 빠르게 전철을 탈 경우 몇 분 만에 타는가?

단, 민수가 출발한 직후인 $0$분에 모든 역에 전철이 도착하며, 전철이 역에 도착했을 때 정차하는 시간은 1분 미만이다.

전철의 정차 시간이 1분 미만이라는 것은, 어떤 전철이 $K$분에 역에 도착했을 때 민수가 $K$분 또는 이전에 그 역에 도착했다면 이 전철을 탑승할 수 있고, 민수가 $K+1$분 또는 이후에 그 역에 도착했다면 이 전철은 탑승할 수 없다는 의미이다.

이러한 질문들에 정확하게 답해보자.

입력

첫째 줄에 $6$개의 정수 $X_1,\ Y_1,\ X_2,\ Y_2,\ X_3,\ Y_3$가 공백으로 구분되어 주어진다. ($-10^5 \leq X_1,\, Y_1,\, X_2,\, Y_2,\, X_3,\, Y_3 \leq 10^5$)

둘째 줄에 질문의 개수 $Q$가 주어진다. ($1 \leq Q \leq 10^5$)

셋째 줄부터 $Q$개의 줄에 각각 질문을 의미하는 정수들인 $X,\ Y,\ T_1,\ T_2,\ T_3$가 공백으로 구분되어 주어진다. ($-10^5 \leq X,\, Y \leq 10^5;\, 1 \leq T_1,\, T_2,\, T_3 \leq 10^5$)

출력

질문이 주어질 때마다 한 줄에 하나씩 정답을 출력한다.

예제 입력 1

-5 -5 5 -5 5 5
3
-1 -1 7 10 6
0 0 3 4 5
0 0 11 12 13

예제 출력 1

10
10
11

신촌역, 대흥역, 서강대역이 각각 $(-5, -5)$, $(5, -5)$, $(5, 5)$에 위치한다.

첫 번째 질문의 경우, 민수는 $(-1, -1)$에서 출발한다.

그러므로 민수가 신촌역으로 가는 데 $|(-1) - (-5)| + |(-1) - (-5)| = 8$분, 대흥역으로 가는 데 $|(-1) - (5)| + |(-1) - (-5)| = 10$분, 서강대역으로 가는 데 $|(-1) - (5)| + |(-1) - (5)| = 12$분이 걸린다.

각 역의 전철이 도착하는 시간은 신촌역은 배차간격이 $7$분이므로 $0,\, 7,\, 14,\, 21,\, \cdots$분에 전철이 도착하고,

대흥역은 배차간격이 $10$분이므로 $0,\, 10,\, 20,\, \cdots$분에 전철이 도착하고,

서강대역은 배차간격이 $6$분이므로 $0,\, 6,\, 12,\, 18,\, \cdots$분에 전철이 도착한다.

가장 빠르게 전철을 탑승하는 방법은 대흥역으로 가는 것이고, $10$분에 오는 전철에 탑승할 수 있다.

두 번째 질문의 경우, 민수가 $(0, 0)$에서 출발하므로 각 전철역에 도착하는 시간은 $10$분으로 동일하다.

이때 민수는 서강대역으로 가서 전철을 탑승한다면 $10$분에 오는 전철을 탈 수 있고, 이 방법이 가장 빠르다.

세 번째 질문의 경우, 민수가 $(0, 0)$에서 출발하므로 각 전철역에 도착하는 시간은 $10$분으로 동일하다.

이때 민수는 신촌역으로 가서 전철을 탑승한다면 $11$분에 오는 전철을 탈 수 있고, 이 방법이 가장 빠르다.

출처

University > 서강대학교 > K512컵 > 2025 서강대학교 K512컵 B번