| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 110 | 36 | 12 | 20.339% |
이 문제는 재우의 재수강 1과 굵은 글씨로 적힌 부분과 제한 조건만 다릅니다.
재우는 제2회 MatKor Cup에서 수영 과목의 F를 막지 못해 결국 재수강을 하게 되었다. 재우는 이번 학기에는 성실히 수영 수업에 임했고, 이제 최종 평가만을 남겨두었다. 최종 평가는 다음과 같이 진행된다.
먼저 수영장을 2차원 좌표계로 표현할 수 있다. 수영장은 왼쪽 아래의 점을 $(0,0),ドル 오른쪽 위의 점을 $(w,h)$로 하는 각 변이 $x$축 혹은 $y$축과 평행한 직사각형이다. 여기서 “수영 가능 영역”이란 직사각형의 네 변과 그 변들로 둘러싸인 영역을 의미한다.
수영장에는 $n$개의 레인이 있고, 각 레인은 $x$축과 평행한 선으로 구분되어 있다. 구체적으로, 0ドル=a_0<a_1<a_2<\cdots <a_n=h$일 때, $i$번째 레인은 $a_{i-1}\le y<a_{i}$인 구간이다. 단, 마지막인 $n$번째 레인은 $a_{n-1}\le y\le a_n$인 구간으로 정의한다.
이 수영장은 최첨단 시스템이 적용되어, 레인별로 물의 밀도가 다르다. 따라서 재우가 이동하는 속도는 어떤 레인에서 수영하느냐에 따라 달라진다. 구체적으로 $i$번째 레인의 물의 밀도가 $p_i$일때, 재우는 1ドル$만큼을 이동하는 데 $p_i$초가 소요된다. 이때, $x$축에서 먼 레인일수록 물의 밀도는 감소한다. 즉, $p_1>p_2>\cdots >p_n$을 만족한다.
재우는 최종 평가를 진행할 때 $(0,0)$에서 출발해 수영 가능 영역에서 수영을 통해서만 이동하여 도착점에 도착해야 한다. 도착점은 $(w,d)$로 수영장의 오른쪽 세로 변 위에 있다. 재우는 출발점에서 출발해서 도착점에 도착할 때까지 걸리는 최단 시간을 알고 싶다.
재우는 수영 가능 영역에서 자유롭게 이동할 수 있다고 할 때, 답을 구해보자.
첫 번째 줄에 수영장의 오른쪽 위의 점을 나타내는 정수 $w$와 $h$가 공백으로 구분되어 주어진다. $(1\le w,h\le 1,000円)$
두 번째 줄에 레인의 개수 $n$과 도착점의 $y$좌표를 나타내는 정수 $d$가 공백으로 구분되어 주어진다. $(1\le n\le 1,000円;$ 0ドル\le d\le h)$
세 번째 줄에 레인의 구분을 나타내는 정수 $a_1,ドル $a_2,ドル $\cdots,ドル $a_n$이 공백으로 구분되어 주어진다. $(0<a_1<a_2<\cdots <a_n=h)$
네 번째 줄에 레인별 물의 밀도 $p_1,ドル $p_2,ドル $\cdots,ドル $p_n$이 공백으로 구분되어 주어진다. $(1\le p_i\le 1,円 000;$ $p_1>p_2>\cdots >p_n)$
도착점에 도착하기까지 걸리는 최단 시간을 출력한다.
정답과의 절대오차 또는 상대오차가 10ドル^{-6}$ 이하이면 정답으로 인정된다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | $n = 1$ |
| 2 | 52 | $n \le 2;$ $d = h$ |
| 3 | 161 | $n \le 2$ |
| 4 | 77 | $d = h$ |
| 5 | 199 | 추가적인 제한 조건 없음 |
3 8 1 4 8 2
10
아래 그림은 정답이 될 수 있는 경로 중 하나이다. 구체적으로 다음과 같은 경로를 지나며, 총 시간은 10ドル$이다.
11 10 2 10 4 10 4 3
50
아래 그림은 정답이 될 수 있는 경로 중 하나이다. 구체적으로 다음과 같은 경로를 지나며, 총 시간은 20ドル + 30 = 50$이다.
25 10 2 4 8 10 5 3
123
아래 그림은 정답이 될 수 있는 경로 중 하나이다. 구체적으로 다음과 같은 경로를 지나며, 총 시간은 50ドル+48+25=123$이다.
5 10 3 10 2 6 10 100 5 1
226.164706
5 10 3 4 2 6 10 100 5 1
226.710751
다행히도 재우는 이번에는 수영 과목에서 Pass를 받았다.
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring N번