| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 27 | 6 | 6 | 60.000% |
BOJ 국가는 좌우로 길쭉한 영토를 가지고 있다. 영토는 수직선 상의 길이 $L$짜리 선분으로 나타낼 수 있으며, 영토의 왼쪽 끝은 좌표 $0$, 오른쪽 끝은 좌표 $L$에 각각 놓여 있다.
BOJ 국가의 영토에는 깃발이 총 $N$개 꽂혀 있는데, 이 중 왼쪽에서 $i$번째 깃발은 정수 좌표 $X_i$에 꽂혀 있다. 깃발이 너무 한 군데에 몰려 있으면 보기에 좋지 않기 때문에, 임의의 두 깃발은 적어도 $K$ 이상의 거리를 가지도록 하는 규정이 있다. 현재 꽂혀 있는 $N$개의 깃발은 이 규정을 지킨다.
신년을 맞이하여 BOJ 국가에서는 깃발 $M$개를 추가로 꽂기로 하였고, BOJ 국가의 공무원인 당신은 이것을 새해 첫 업무로 배정받았다. 깃발을 꽂기 위해서 당신은 특정 좌표에서 깃발 $M$개를 들고 출발한다. 당신은 영토 내에서 좌우로 자유롭게 이동할 수 있으며, 현재 서 있는 위치가 정수 좌표라면 언제든지 깃발을 꽂을 수 있다. 단, 규정을 지키기 위해서 이미 꽂힌 깃발을 포함하여 임의의 두 깃발이 적어도 $K$ 이상의 거리를 가지도록 깃발 $M$개를 꽂아야 한다. 규정을 지키면서 깃발 $M$개를 꽂을 수 없는 경우는 주어지지 않는다.
당신은 가능한 출발지로 총 $Q$개의 후보를 골라 이 중 하나에서 출발하기로 했으며, $i$번째 후보는 정수 좌표 $P_i$에 위치한다. 이동 거리가 길수록 퇴근이 늦어지기 때문에, 당신은 각 후보에서 출발할 때 $M$개의 깃발을 모두 꽂는 데에 필요한 최소 이동 거리를 알고 싶다. 빠른 퇴근을 위해 이 값들을 구하여 보자.
첫 번째 줄에 $N$, $M$, $K$, $L$, $Q$가 공백으로 구분되어 주어진다.
두 번째 줄에 $N$개의 정수 $X_i$가 공백으로 구분되어 주어진다.
이후 $Q$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 $P_i$가 주어진다.
$Q$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 $i$번째 후보에서 출발할 때 $M$개의 깃발을 모두 꽂는 데 필요한 최소 이동 거리를 출력한다.
3 3 2 20 5 5 10 19 12 4 2 20 9
4 9 7 7 7
예제에서 $M=3$, $K=2$이다. 즉, 깃발 3개를 추가로 꽂아야 하며, 임의의 두 깃발은 최소 2만큼 떨어져 있어야 한다.
첫 번째 후보인 좌표 12에서 출발할 경우, 16까지 이동하면서 12, 14, 16에 깃발 3개를 꽂으면 이동 거리가 4가 된다. 더 짧게 움직이는 방법은 없으므로 답은 4이다.
두 번째 후보인 좌표 4에서 출발할 경우, 우선 7까지 이동하여 7에 깃발 하나를 꽂고, 다시 1까지 이동하면서 3, 1에 깃발 2개를 더 꽂으면 이동 거리가 9가 된다. 더 짧게 움직이는 방법은 없으므로 답은 9이다.
Contest > BOJ User Contest > Good Bye, BOJ > Hello, BOJ 2024! F번