추월 (Overtaking)

overtaking
English (ISC)
추월 (Overtaking)
부다페스트 공항에서 Forrás 호텔까지 1차선 일방통행 도로가 있다. 도로의 길이는 L 킬로미터이다.
IOI 2023 행사 기간 동안 N + 1대의 셔틀버스가 이 도로를 지난다. 버스에는 0부터 N까지 번호가 매겨져 있다. 버스 i (0 ≤i < N)는 행사 시작 후 T[i]초에 공항을 출발할 예정이며, 1킬로미터를 W[i]초에 갈 수 있다. 버스 N은 예비 버스로, 1킬로미터를 X초에 갈 수 있다. 예비 버스가 공항을 출발할 시각 Y 는 아직 정해지지 않았다.
이 도로에서는 원칙적으로 추월이 허용되지 않지만, 정렬 지점에서는 버스들이 서로 추월할 수 있다. 도로 위의 서로 다른 위치에 M개 (M > 1)의 정렬 지점이 있으며, 0부터 M −1까지 번호가 매겨져 있다. 정렬 지점 j (0 ≤j < M )는 도로를 따라 공항으로부터 S[j] 킬로미터 지점에 있다. 정렬 지점들은 공항으로부터의 거리가 증가하는 순으로 정렬되어 있다. 즉, 0 ≤j ≤M −2인 각 j에 대해 S[j] < S[j + 1]이다. 첫 번째 정렬 지점은 공항이고 마지막은 호텔이다. 즉, S[0] = 0이고 S[M −1] = L이다.
각 버스는 도로에서 앞서가는 더 느린 버스를 따라잡지 않는 한 최대 속도로 달린다. 따라잡으면 두 버스는 한 무리가 되어 다음 정렬 지점에 도착할 때까지 느린 버스의 속도로 달릴 수밖에 없다. 그곳에서 빠른 버스들이 느린 버스들을 추월한다.
형식적으로, 0 ≤i ≤N이고 0 ≤j < M인 각 i, j에 대해, 버스 i가 정렬 지점 j에 도착하는 시각 t
(초 단위)는 다음과 같이 정의된다. 각 0 ≤i < N에 대해 t
= T[i]로 두고,
t
= Y 로 둔다. 0 < j < M인 각 j에 대해:
버스 i의 정렬 지점 j 도착 예정 시각(초 단위)
e
를, 버스 i가 정렬 지점 j −1에 도착한 시각부터 최대 속도로 달렸을 때 정렬 지점 j에 도착하는 시각으로 정의한다. 즉,
각 0 ≤i < N에 대해 e
= t
+ W[i] ⋅(S[j] −S[j −1]), 그리고
e
= t
+ X ⋅(S[j] −S[j −1])로 둔다.
버스 i는 자신의 도착 예정 시각과, 자신보다 먼저 정렬 지점 j −1에 도착한 다른 모든 버스의 도착 예정 시각 중 최댓값의 시각에 정렬 지점 j에 도착한다. 형식적으로, t
를
e
와, 0 ≤k ≤N이고 t
< t
인 모든 e
중 최댓값으로 둔다.
IOI 조직위원회는 예비 버스(버스 N)의 운행 일정을 정하려고 한다. 여러분의 과제는 조직위원회의 다음 형태의 질문 Q개에 답하는 것이다. 예비 버스가 공항을 출발할 시각 Y (초 단위)가 주어졌을 때, 예비 버스는 몇 시에 호텔에 도착하는가?
i,j
i,0
N,0
i,j
i,j
i,j−1
N,j
N,j−1
i,j
i,j
k,j
k,j−1
i,j−1
overtaking (1 of 5)

Implementation Details
다음 프로시저들을 구현해야 한다.
void init(int L, int N, int64[] T, int[] W, int X, int M, int[] S)
L: 도로의 길이.
N: 예비 버스가 아닌 버스의 수.
T: 예비 버스가 아닌 버스들이 공항을 출발할 예정 시각을 나타내는 길이 N의 배열.
W: 예비 버스가 아닌 버스들의 최대 속도를 나타내는 길이 N의 배열.
X: 예비 버스가 1킬로미터를 가는 데 걸리는 시간.
M : 정렬 지점의 수.
S: 정렬 지점들의 공항으로부터의 거리를 나타내는 길이 M의 배열.
이 프로시저는 각 테스트 케이스마다 arrival_time 호출 전에 정확히 한 번 호출된다.
int64 arrival_time(int64 Y)
Y : 예비 버스(버스 N)가 공항을 출발할 예정 시각.
이 프로시저는 예비 버스가 호텔에 도착하는 시각을 반환해야 한다.
이 프로시저는 정확히 Q번 호출된다.
Example
다음 호출 순서를 생각해 보자.
init(6, 4, [20, 10, 40, 0], [5, 20, 20, 30], 10, 4, [0, 1, 3, 6])
(아직 일정이 정해지지 않은) 버스 4를 무시하면, 다음 표는 예비 버스가 아닌 버스들의 각 정렬 지점 도착 예정 시각과 실제 도착 시각을 보여 준다.
i
t
e
t
e
t
e
t
0
20
25
30
40
40
55
55
1
10
30
30
70
70
130
130
2
40
60
60
100
100
160
180
3
0
30
30
90
90
180
180
정렬 지점 0에서의 도착 시각은 버스들이 공항을 출발할 예정 시각이다. 즉, 0 ≤i ≤3에 대해 t
= T[i]이다.
정렬 지점 1에서의 도착 예정 시각과 실제 도착 시각은 다음과 같이 계산된다.
i,0
i,1
i,1
i,2
i,2
i,3
i,3
i,0
overtaking (2 of 5)

정렬 지점 1 도착 예정 시각:
버스 0: e
= t
+ W[0] ⋅(S[1] −S[0]) = 20 + 5 ⋅1 = 25.
버스 1: e
= t
+ W[1] ⋅(S[1] −S[0]) = 10 + 20 ⋅1 = 30.
버스 2: e
= t
+ W[2] ⋅(S[1] −S[0]) = 40 + 20 ⋅1 = 60.
버스 3: e
= t
+ W[3] ⋅(S[1] −S[0]) = 0 + 30 ⋅1 = 30.
정렬 지점 1 도착 시각:
버스 1과 3이 버스 0보다 먼저 정렬 지점 0에 도착하므로 t
= max([e
,e
,e
]) = 30.
버스 3이 버스 1보다 먼저 정렬 지점 0에 도착하므로 t
= max([e
,e
]) = 30.
버스 0, 버스 1, 버스 3이 버스 2보다 먼저 정렬 지점 0에 도착하므로
t
= max([e
,e
,e
,e
]) = 60.
버스 3보다 먼저 정렬 지점 0에 도착하는 버스는 없으므로 t
= max([e
]) = 30.
arrival_time(0)
버스 4는 1킬로미터를 가는 데 10초가 걸리고, 이제 0초에 공항을 출발할 예정이다. 이 경우 다음 표는 각 버스의 도착 시각을 보여 준다. 예비 버스가 아닌 버스들의 도착 예정 시각 및 실제 도착 시각에서 유일하게 바뀐 부분은 밑줄로 표시되어 있다.
i
t
e
t
e
t
e
t
0
20
25
30
40
40
55
1
10
30
30
70
70
130
130
2
40
60
60
100
100
160
180
3
0
30
30
90
90
180
180
4
0
10
10
30
30
60
60
버스 4는 60초에 호텔에 도착함을 알 수 있다. 따라서 이 프로시저는 60을 반환해야 한다.
arrival_time(50)
버스 4는 이제 50초에 공항을 출발할 예정이다. 이 경우 예비 버스가 아닌 버스들의 도착 시각은 처음 표와 비교해 달라지지 않는다. 도착 시각은 다음 표와 같다.
0,1
0,0
1,1
1,0
2,1
2,0
3,1
3,0
0,1
0,1
1,1
3,1
1,1
1,1
3,1
2,1
0,1
1,1
2,1
3,1
3,1
3,1
i,0
i,1
i,1
i,2
i,2
i,3
i,3
60
overtaking (3 of 5)

i
t
e
t
e
t
e
t
0
20
25
30
40
40
55
55
1
10
30
30
70
70
130
130
2
40
60
60
100
100
160
180
3
0
30
30
90
90
180
180
4
50
60
60
80
90
120
130
버스 4는 정렬 지점 1에서 더 느린 버스 2와 동시에 도착하므로 그곳에서 버스 2를 추월한다. 다음으로 버스 4는 정렬 지점 1과 2 사이에서 버스 3과 한 무리가 되어, 80초가 아닌 90초에 정렬 지점 2에 도착하게 된다. 정렬 지점 2를 떠난 뒤 버스 4는 호텔에 도착할 때까지 버스 1과 한 무리가 된다. 버스 4는 130초에 호텔에 도착한다. 따라서 이 프로시저는 130을 반환해야 한다.
각 버스가 공항으로부터의 각 거리에 도달하는 데 걸리는 시간을 그래프로 그릴 수 있다. 그래프의 x축은 공항으로부터의 거리(킬로미터), y축은 시간(초)을 나타낸다. 세로 점선은 정렬 지점의 위치를 나타낸다. 서로 다른 실선(버스 번호가 함께 표시됨)은 예비 버스가 아닌 네 버스를 나타낸다. 검은 점선은 예비 버스를 나타낸다.
arrival_time(0)
arrival_time(50)
Constraints
i,0
i,1
i,1
i,2
i,2
i,3
i,3
overtaking (4 of 5)

1 ≤L ≤10
1 ≤N ≤1 000
0 ≤T[i] ≤10
(0 ≤i < N인 각 i에 대해)
1 ≤W[i] ≤10 (0 ≤i < N인 각 i에 대해)
1 ≤X ≤10
2 ≤M ≤1 000
0 = S[0] < S[1] < ⋯< S[M −1] = L
1 ≤Q ≤10
0 ≤Y ≤10
Subtasks
1. (9 points) N = 1,Q ≤1 000
2. (10 points) M = 2,Q ≤1 000
3. (20 points) N,M,Q ≤100
4. (26 points) Q ≤5 000
5. (35 points) 추가 제약 없음.
Sample Grader
샘플 그레이더는 다음 형식으로 입력을 읽는다.
line 1: L N X M Q
line 2: T[0] T[1] ... T[N −1]
line 3: W[0] W[1] ... W[N −1]
line 4: S[0] S[1] ... S[M −1]
line 5 + k (0 ≤k < Q): 질문 k의 Y
샘플 그레이더는 여러분의 답을 다음 형식으로 출력한다.
line 1 + k (0 ≤k < Q): 질문 k에 대한 arrival_time 의 반환값
9
18
9
9
6
18
overtaking (5 of 5)

이 저지에서의 입출력

이 문제는 IOI의 함수 구현형 문제 overtaking을 표준 입출력 방식으로 각색한 것이다. 함수를 구현하는 대신, 아래의 공식 그레이더(내부 부정행위 방지 검사는 제거됨)가 하는 것과 정확히 같은 방식으로 표준 입력에서 함수의 인자를 읽고 반환값을 표준 출력으로 출력하면 된다. 또는 그레이더 코드에 자신의 함수 구현을 붙여 그대로 제출해도 된다.

함수 시그니처 (overtaking.h):

#include <vector>

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S);

long long arrival_time(long long Y);

참고용 입출력 드라이버 (공식 그레이더, 정리본):

#include "overtaking.h"
#include <cassert>
#include <cstdio>
#include <vector>

int main()
{
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}

rip 작성

출처 IOI 2023