시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 58 | 13 | 11 | 21.154% |
상근이는 근처 산에 차를 타고 올라왔다. 상근이는 다가올 ICPC를 준비해야 하기 때문에, 최대한 빨리 집으로 가려고 한다. 하지만, 차에 기름이 얼마 남지 않았기 때문에, 최대한 효율적으로 운전해야 한다.
길의 일부는 오르막길이고, 일부는 내리막길이다. 각 길은 모두 서로 다른 길이와 경사를 가지고 있다. 상근이의 차에 남은 기름의 양이 주어졌을 때, 얼마나 빨리 집으로 돌아올 수 있는지 구하는 프로그램을 작성하시오.
상근이의 차의 기름 소비량은 단순하게 모델링할 수 있다. 연료 소비량 (단위 거리당 연료 소비) 은 자동차의 속도 \(v\)에 비례해서 증가한다. 또, 언덕의 기울기 \(s\)에 의해 오프셋이 결정된다.
예를 들어, 연료를 사용하지 않고 10km/h로 내려갈 수 있는 언덕이 있다고 하자. 이 도로를 올라갈 때는 사용하는 연료의 양은 평지에서 10km/h 빠르게 이동할 때 사용하는 양과 같다. 연료 소비량 \(c\)(리터/km)는 아래와 같은 식으로 나타낼 수 있다.
\[c=max(0,\alpha v + \beta s)\]
\(\alpha\)는 평지에서 연료 소비량, \(v\)는 자동차의 속도(km/h), \(s\)는 언덕의 기울기, \(\beta\)는 양수 상수이다. 가속과 감속은 연료를 사용하지 않으며, 즉시 이루어진다.
자동차는 최고 속도가 있어서, 이 속도를 넘을 수 없다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100개를 넘지 않는다.
첫째 줄에 네 정수 \(\alpha\) (1 ≤ \(\alpha\) ≤ 100), \(\beta\) (0.1 ≤ \(\beta\) ≤ 100), \(v_{max}\) (10 ≤ \(v_{max}\) ≤ 200), \(f\) (0 ≤ \(f\) ≤ 50) 가 주어진다. \(v_{max}\)는 자동차의 최고 속도이고, \(f\)는 자동차에 남은 기름의 양(리터) 이다.
다음 줄에는 도로의 수 r (1 ≤ r ≤ 10,000)이 주어진다.
다음 r개 줄에는 두 실수 xi와 yi가 주어진다. (1 ≤ xi ≤ 1000, -1000 ≤ yi ≤ 1000) xi는 i번째 도로의 길이, yi는 높이의 변화를 나타낸다. 각 도로의 기울기는 일정하다.
각 테스트 케이스마다 집으로 돌아오는 가장 빠른 시간을 출력한다. 집으로 돌아올 수 있는 경우에는 항상 걸리는 시간이 24 시간보다 작다. 만약, 집으로 돌아올 수 없으면 "IMPOSSIBLE"을 출력한다. 정답의 상대/절대 오차는 최대 10-6까지 허용한다.
3 10.0 1.0 150 0.0 1 100.0 -100.0 10.0 100.0 150 1.0 2 100 0 100 100 0.5 0.1 100 10 3 1000 0 100 10 100 -10
1.414214 IMPOSSIBLE 0.072120
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2010 D번