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

문제

중부 내륙선은 2021년 12월 31일에 개통된 단선 철도입니다. 하행 열차는 부발역을 출발하여 가남, 감곡장호원, 앙성온천, 충주 순으로 멈추고, 상행 열차는 충주를 출발하여 앙성온천, 감곡장호원, 가남, 부발역 순으로 멈춥니다. 각 구간의 소요 시간은 [표 1]과 같습니다.

구간 소요 시간
부발 ~ 가남 7
가남 ~ 감곡장호원 7
감곡장호원 ~ 앙성온천 8
앙성온천 ~ 충주 10

[표 1] 각 구간의 소요 시간

중부내륙선은 단선이어서, 구간에는 한 열차만 운행할 수 있습니다. 하지만, 역에는 상행 열차 여러 대와 하행 열차 여러 대가 동시에 정차할 수 있습니다. 하행 열차와 상행 열차는 아래 알고리즘으로 운행됩니다.

순번 하행 상행
1 부발역에서 HH시 mm분에 문을 닫는다. 충주역에서 HH시 mm분에 문을 닫는다.
2 구간 부발 ~ 가남을 운행한다. 구간 앙성온천 ~ 충주를 운행한다.
3 1분간 가남역에 머무르고 문을 닫는다. 1분간 앙성온천역에 머무르고 문을 닫는다.
4 구간 가남 ~ 감곡장호원을 운행한다. 구간 감곡장호원 ~ 앙성온천을 운행한다.
5 1분간 감곡장호원역에 머무르고 문을 닫는다. 1분간 감곡장호원역에 머무르고 문을 닫는다.
6 구간 감곡장호원 ~ 앙성온천을 운행한다. 구간 가남 ~ 감곡장호원을 운행한다.
7 1분간 앙성온천역에 머무르고 문을 닫는다. 1분간 가남역에 머무르고 문을 닫는다.
8 구간 앙성온천 ~ 충주를 운행한다. 구간 부발 ~ 가남을 운행한다.
9 충주역에 도착하면 운행을 종료한다. 부발역에 도착하면 운행을 종료한다.

[표 2] 하행, 상행 열차의 운행 알고리즘

표 2는 하행 열차와 상행 열차가 시발역에서 종착역까지 가기 위해서 수행하는 일들을 나타냅니다. 이 중 순번 2, 4, 6, 8은 구간을 운행하는 것이므로 관제의 허가를 받아야 합니다. 허가를 받지 못하면 받을 때까지 대기했다가 수행합니다. 하행에서의 A역 다음 역이 B역이라고 했을 때, 관제는 구간 A ~ B에 대해서

  1. 구간 A ~ B를 운행하는 열차가 있는 경우, 다른 열차가 구간 A ~ B에 접근하는 것을 허용하지 않습니다.
  2. 그렇지 않은 경우
    1. A역에서 구간 A ~ B를 운행하려고 하는 하행 열차 h만 있다면, h가 구간 A ~ B를 운행하는 것을 허용합니다.
    2. B역에서 구간 A ~ B를 운행하려고 하는 상행 열차 s만 있다면, s가 구간 A ~ B를 운행하는 것을 허용합니다.
    3. 그렇지 않은 경우
      1. 시발역에서 먼저 운행을 시작한 열차가 구간A ~ B를 운행하는 것을 허용합니다.
      2. 2 - 3 - 1로도 결정할 수 없다면, 편성 번호가 더 낮은 열차가 구간 A ~ B를 운행하는 것을 허용합니다.

충주로 향하는 하행 열차 C편성, 부발로 향하는 상행 열차 H편성이 있을 때, 각 편성이 종착역에 도착하는 시각을 구해 주세요. 

입력

첫 번째 줄에 CH가 공백을 구분으로 해서 주어집니다.

다음 C개의 줄에는 충주로 향하는 하행 열차의 번호와, 해당 열차가 시발역에서 운행을 시작한 시각이 HH:mm형식으로 주어집니다.

다음 H개의 줄에는 부발로 향하는 상행 열차의 번호와, 해당 열차가 시발역에서 운행을 시작한 시각이 HH:mm형식으로 주어집니다.

출력

각 열차가 종착 (상행선의 경우 부발, 하행선의 경우 충주)역에 도착하는 시각을 열차 번호 오름차순으로 출력해 주세요. 시각은 HH:mm형식으로 출력해 주세요.

자정이 넘어 도착하는 경우, 다음날 HH:mm 에 도착했다고 출력해 주세요.

제한

  • HC는 1 이상 20 이하의 정수입니다.
  • 주어지는 열차 번호는 다음 조건을 따릅니다.
    • 3자리로 주어집니다.
    • 상행선의 열차 번호는 끝자리가 짝수로, 하행선의 열차 번호는 끝자리가 홀수로 주어집니다.
    • 같은 목적지로 향하는 열차에 대해, 먼저 출발한 열차의 열차 번호는 나중에 출발한 열차의 번호보다 작습니다.
  • 시발역에서 방향이 같은 둘 이상의 열차가 동시에 출발하지 않습니다.
  • 시각은 HH:mm형식입니다. 이때, HH는 0 이상 23 이하의 정수로, mm은 0 이상 59 이하의 정수로 주어집니다. HHmm은 10보다 작으면 앞에 0이 붙습니다.

예제 입력 1

1 1
731 07:10
732 07:20

예제 출력 1

07:45
07:58

731 열차가 감곡장호원 역을 출발한 07시 26분에, 731과 732의 상황은 [표 3]과 같습니다.

편성 수행하고 있는 알고리즘 알고리즘을 마치는 시각
731 감곡장호원역을 출발, 감곡장호원 ~ 앙성온천 구간 운행중 07시 34분
732 충주역을 출발, 앙성온천 ~ 충주 구간 운행중 07시 30분

[표 3] 731과 732의 07시 26분에 수행하고 있는 알고리즘

732가 감곡장호원 ~ 앙성온천 구간을 운행하기 위해, 관제의 허가를 받습니다. 그런데, 관제는 731이 감곡장호원 ~ 앙성온천을 운행하고 있기 때문에, 관제는 731이 앙성온천역에 도착할 때 까지 732가 감곡장호원 ~ 앙성온천 구간에 접근하는 것을 허용하지 않습니다. 732가 해당 구간에 접근하는 것은 7시 34분이므로, 앙성온천역에 예정보다 3분 더 머무르게 됩니다. 따라서, 732는 종착역에 3분 늦게 도착합니다.

예제 입력 2

2 1
731 07:10
733 07:18
732 23:50

예제 출력 2

07:45
00:25
07:55

731은 733의 선행 열차이고, 732는 731보다 16시간 40분 뒤에 출발합니다. 따라서, 731은 부발에서 충주까지 가는 데 35분이 걸립니다. 733은 731의 후행 열차이므로, 733이 구간에 들어가려고 할 때, 731이 해당 구간에 운행을 할 수 있습니다. [표 4]는 731과 733이 언제 운행 알고리즘을 수행하는지 나타냅니다.

순번 731 733
1 07:10 07:18
2 07:10 ~ 07:17 07:18 ~ 07:25
3 07:17 ~ 07:18 07:25 ~ 07:26
4 07:18 ~ 07:25 07:26 ~ 07:33
5 07:25 ~ 07:26 07:33 ~ 07:34
6 07:26 ~ 07:34 07:34 ~ 07:42
7 07:34 ~ 07:35 07:42 ~ 07:43
8 07:35 ~ 07:45  
9 07:45  

[표 4] 731과 733의 운행 알고리즘을 수행하는 시각

[표 4]에서, 731이 앙성온천 ~ 감곡 구간을 07시 35분부터 07시 45분까지 운행함을 알 수 있습니다. 733은 앙성온천역에 07시 42분에 도착하였고, 1분간 머무른 다음 07시 43분에 순번 8을 수행하려고 합니다. 그런데, 이미 731이 순번 8을 07시 45분까지 수행하고 있으므로, 733은 앙성온천역에 2분 더 머무르게 됩니다. 따라서, 733은 종착역인 충주역에 2분 늦게 도착합니다.

예제 입력 3

1 1
731 07:32
732 07:20

예제 출력 3

08:14
07:55

731 열차는 가남역에 07시 39분에, 732 열차는 감곡장호원역에 07시 39분에 도착합니다. 07시 40분에 두 열차는 가남 ~ 감곡장호원 구간을 운행하기 위해 관제에 허가를 받아야 합니다. 관제는 기준 2 - 3 - 1에 따라 시발역에서 먼저 운행을 시작한 732 열차에게 가남 ~ 감곡장호원 구간을 운행하는 것을 허가합니다. 그 이후에 일어나는 일들은 [표 6]과 같습니다.

시간 731 732
07:40 가남역에서 대기 가남 ~ 감곡장호원 구간 운행
07:47 732가 가남에 도착했으므로
가남역 출발
가남역 도착
... ... ...
  정시보다 7분 늦게 충주 도착 정시에 부발 도착

[표 6] 731과 732가 가남 ~ 감곡장호원 구간을 운행하는 시각

예제 입력 4

1 1
731 07:10
732 23:50

예제 출력 4

07:45
00:25

힌트

  • 시발역은 열차가 운행을 시작하는 역이고, 종착역은 열차가 운행을 마치는 역입니다.
  • 문제의 단순화를 위해 아래의 요소들은 무시하셔도 좋습니다.
    • 앙성온천 ~ 충주 구간에 있는 금가 신호장
    • 부발역 근처에서 경강선 전철과의 경합
    • 부발 기지에 속해 있는 이음 편성의 수