3660번 - 열차 지연 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 21 | 8 | 5 | 38.462% |
문제
작년에 알고스팟 운영진들은 ACM-ICPC 대전 대회에 가기 위해 기차를 타고 이동했다. 하지만, 이것은 곧 엄청난 재앙으로 이어졌다. 대전으로 갈 때는 대전역에 발생한 불로 인해 열차가 지연되었고, 서울로 돌아올 때는 서울에 대한 테러 위협때문에 기차가 엄청나게 지연되었다. 이러한 엄청난 열차의 지연은 다른 열차도 지연되게 만든다. 느린 열차를 타는 것과 급행 열차를 기다리는 것 중 어떤 것이 열차가 지연될 확률이 적을까?
올해 알고스팟 운영진들은 열차 스케줄을 분석하고 계획을 세우기로 했다. 그들은 기차가 얼마나 지연되고, 얼마나 자주 지연되는지를 조사했다. 이제 이 정보를 가지고 이동 시간의 기댓값이 가장 작은 열차를 타려고 한다.
각각의 열차에 대해서 알고스팟 운영진은 출발 시간과 소요 시간을 정확하게 알고 있다. 또, 그 열차가 지연될 확률도 알고 있다. 열차가 지연될 확률은 독립이고, 가는 도중에 지연되는 열차가 발생하면, 그 지연을 반영해서 여행 계획을 바꿀 수 있다.
열차는 항상 정시에 출발한다. 하지만, 도착 시간은 지연될 수 있다. 알고스팟 운영진은 열차가 지연될지 말지를 열차가 출발하기 전까지 알 수 없다. 알고스팟 운영진이 열차를 환승하는데 드는 시간은 0이다. 따라서, 열차가 도착한 시간과 동시에 출발하는 시간의 열차를 탈 수 있다.
알고스팟 운영진은 첫 기차를 타는 시간을 마음대로 정할 수 있다. 기차를 타고 이동하는데 드는 시간의 기댓값의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 출발 도시의 이름과 도착 도시의 이름이 주어진다. 출발 도시와 도착 도시의 이름이 같은 경우는 없다. 그 다음 줄에는 열차의 수 n (1 ≤ n ≤ 1000)이 주어진다. 다음 n개의 줄에는 한 줄에 하나씩 열차의 정보가 주어진다.
열차의 정보는 다음과 같이 구성되어져 있다.
- 출발 도시와 도착 도시. 두 도시의 이름이 같은 경우는 없다.
- 열차의 출발 시간 m (0 ≤ m ≤ 59). 열차는 항상 1시간에 한 편씩 있으며, m분에 출발한다.
- 열차의 소요 시간 t ( 1 ≤ t ≤ 300). 열차가 지연되지 않았을 때 걸리는 시간이다.
- 열차가 지연될 퍼센트 확률 p (0 ≤ p ≤ 100).
- 열차의 최대 지연 시간 d (1 ≤ d ≤ 120). d의 단위는 분이다.
모든 도시의 이름은 알파벳 대문자와 소문자로만 이루어져 있으며, 길이는 20을 넘지 않는다. 열차는 항상 정수 분 만큼 지연되며, 확률은 구간 [1, d]에 균일하게 분포되어 있다.
출력
각 테스트 케이스에 대해서 여행을 하는데 걸리는 시간의 기댓값의 최솟값을 출력한다.
만약, 도착 도시에 갈 수 없는 경우에는 "IMPOSSIBLE"을 출력하며, 소수점 오차는 10-6까지 허용한다.
예제 입력 1
3 Seoul Daejeon 3 Seoul Daejeon 15 68 10 5 Seoul Daejeon 46 55 50 60 Daejeon Busan 14 226 10 120 Seoul Daejeon 1 Seoul Busan 10 22 5 10 Seoul Daejeon 9 Seoul Gwangmyeong 15 10 0 1 Seoul Gwangmyeong 45 10 0 1 Seoul Cheonan 23 140 10 15 Gwangmyeong Busan 44 51 60 70 Busan Incheon 55 147 38 40 Incheon Daejeon 24 15 30 15 Incheon Daejeon 54 15 10 35 Cheonan Anyang 45 140 5 10 Anyang Incheon 46 96 10 20
예제 출력 1
68.3 IMPOSSIBLE 305.0532857
힌트
첫 번째 예제에서 서울에서 대전으로 이동할 때, 느린 열차를 타는 것이 더 좋다. 빠른 열차의 소요 시간의 기댓값은 70.25분이다.
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 J번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호