시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

노르웨이에는 땅과 피오르드(강이라고 생각하면 된다)가 반복되며 나타난다. 따라서 이동을 하기 위해서는 땅에서는 운전을 하고, 피오르드에서는 이미 갖춰진 배들을 이용하여 건너야 한다.

가장 빠른 시간에 이동하는 방법은, 땅에서는 최고 속도인 80km/h로 운전을 하고, 피오르드에 도착해 배를 기다리고, 배를 타고 다음 위치로 가서 반복하는 것이다. 하지만 이와 같이 이동하는 것은 비싸기도 하고, 환경 친화적이지도 않다. 따라서 당신은 우선 가장 빠른 시간에 이동하는 방법을 찾고, 그와 동시에 운전 속도도 최소화해야 한다.

입력

입력 파일에는 여러 개의 데이터가 들어 있다. 첫째 줄에는 s(s>0)가 주어진다. 이는 이동할 때의 구역의 개수이다. 다음 s개의 줄에는 각 구역에 대한 정보가 이동해야 하는 순서대로 주어져 있다. 각 구역에 대한 정보는 시작 위치와 끝 위치의 이름으로 시작된다. 그 다음에는 땅이라면 road, 피오르드라면 ferry가 주어진다.

Dryna Solholmen road 32

road의 경우에는 그 다음에 양의 정수로 땅의 길이가 km단위로 주어진다. 위의 예는 Dryna에서 Solholmen까지는 땅으로 되어 있으며 그 길이는 32km라는 것이다.

Manhiller Fodnes ferry 20 2 15 35

ferry의 경우에는 우선 배를 타고 건너는 시간이 양의 정수로 주어진다. 이 시간의 단위는 분으로, 위의 예에서는 20분이 된다. 다음 수 f(f>0)는 각 시간에 운행되는 배의 개수이다. 다음 f개의 정수들은 각 배가 출발하는 시간이 분으로 주어진다. 위의 예에서는 배들이 0:15, 0:35, 1:15, 1:35, 2:15, … 와 같이 운행된다는 의미이다. 이 f개의 정수들은 증가하는 순서로 입력된다.

각각의 데이터는 총 이동 시간이 10시간을 넘지 않도록 설계되어 있다. 또한 이동은 항상 정각(x시 0분)에 시작된다고 가정하자. 만약 s=0이 주어지면 입력이 끝난 것이다.

출력

각 줄에 데이터 번호, 최소 이동 시간, 이동 시간이 최소일 때의 최소 운전 속도를 출력한다. 속도는 소수점 아래 셋째 자리에서 반올림해서 출력한다.

예제 입력

1
Bygd Bomvei road 7
2
Ferje Overfarten ferry 20 2 5 25
Overfarten Havneby ferry 30 3 10 30 50
5
Begynnelse Brygge road 30
Brygge Bestemmelse ferry 15 4 10 25 40 55
Bestemmelse Veiskillet road 20
Veiskillet Grusvei road 25
Grusvei Slutt ferry 50 1 10
0

예제 출력

Test Case 1: 00:05:15 80.00
Test Case 2: 01:00:00 0.00
Test Case 3: 03:00:00 45.00

힌트

확인해 보면 알겠지만 입력 데이터의 크기의 제한이 주어져 있지 않다. 따라서 최적의 알고리즘을 찾아보고, 그 알고리즘이 견딜 수 있을 정도를 입력 범위로 하면 된다.