라우터 찾기 (routers)

왼쪽에서 오른쪽으로 뻗은 길이 $l$미터의 도로가 있으며, 서로 다른 여러 위치에 $n$개의 작은 라우터가 놓여 있다. 도로의 가장 왼쪽 지점을 원점이라고 정의한다. 라우터에는 왼쪽부터 오른쪽까지 $0$부터 $n-1$까지의 번호가 붙어 있으며, 라우터 $i$는 원점에서 $p[i]$미터 떨어진 곳에 놓여 있다.

라우터 $0$은 원점에 있으며, 각 라우터에서 원점까지의 거리를 미터 단위로 나타낸 값은 짝수인 정수임이 보장된다.

$n$개 라우터 각각의 위치를 알아내고자 한다. 라우터는 매우 작아서 멀리서는 찾기 어렵기 때문에, 다음 절차를 사용하여 라우터를 찾기로 했다.

• 원점에서 $x$미터 떨어진 지점에 탐지기를 놓는다.
• 탐지기를 사용하여 탐지기에서 가장 가까운 라우터의 번호를 알아낸다. 탐지기로부터 같은 거리만큼 떨어진 라우터가 두 개 있다면, 번호가 더 작은 라우터를 응답한다.

탐지기는 최대 $q$번 사용할 수 있다. 모든 라우터의 위치를 찾는 전략을 고안하라.

구현 세부사항

다음 프로시저를 구현해야 한다.

int[] find_routers(int l, int n, int q)

• $l$: 도로의 길이(미터 단위).
• $n$: 라우터의 개수.
• $q$: 탐지기를 사용할 수 있는 최대 횟수.
• 이 프로시저는 그레이더에 의해 정확히 한 번 호출된다.
• 각 라우터의 위치를 나타내는 배열 $p$를 반환해야 하며, $p[i]$는 라우터 $x$와 원점 사이의 거리이다.

위 프로시저에서는 다음 프로시저를 호출할 수 있다.

int use_detector(int x)

• $x$: 탐지기와 원점 사이의 거리.
• $x$는 $0$ 이상 $l$ 이하여야 한다.
• 이 프로시저는 탐지기에서 가장 가까운 라우터의 번호를 반환한다. 탐지기로부터 같은 거리만큼 떨어진 라우터가 두 개 있다면, 더 작은 번호를 반환한다.
• 이 프로시저는 $q$번을 초과하여 호출할 수 없다.

예제

예제 1

다음 호출을 생각해 보자.

find_routers(5, 2, 10)

길이 $5$미터인 도로에 라우터가 $2$개 있으며, use_detector를 최대 $10$번 호출할 수 있다. 라우터가 원점으로부터 각각 $0$미터와 $4$미터 떨어진 곳에 놓여 있다고 하자.

find_routers 프로시저는 use_detector(3)을 호출할 수 있다. 위치 $4$에 있는 라우터 $1$이 탐지기에서 가장 가까우므로 이 호출은 $1$을 반환한다.

그런 다음 find_routers 프로시저는 use_detector(2)를 호출할 수 있다. 라우터 $0$과 $1$이 모두 탐지기로부터 같은 거리만큼 떨어져 있고 라우터 $0$의 번호가 더 작으므로 이 호출은 $0$을 반환한다.

이 시점에는 라우터가 각각 위치 $0$과 $4$에 있다고 결론 내리기에 충분한 정보가 있다.

따라서 find_routers 프로시저는 [$0$, $4$]를 반환해야 한다.

예제 2

다음 호출을 생각해 보자.

find_routers(6, 3, 10)

길이 $6$미터인 도로에 라우터가 $3$개 있으며, use_detector를 최대 $10$번 호출할 수 있다. 라우터가 원점으로부터 각각 $0$미터, $2$미터, $6$미터 떨어진 곳에 놓여 있다고 하자.

find_routers 프로시저는 use_detector(5)를 호출할 수 있다. 라우터 $2$가 위치 $6$에 있어 탐지기에서 가장 가까우므로 이 호출은 $2$를 반환한다.

그런 다음 find_routers 프로시저는 use_detector(4)를 호출할 수 있다. 라우터 $1$과 $2$가 탐지기로부터 같은 거리만큼 떨어져 있으므로 이 호출은 $1$을 반환한다.

이 시점에는 라우터가 각각 위치 $0$, $2$, $6$에 있다고 결론 내리기에 충분한 정보가 있다.

따라서 find_routers 프로시저는 [$0$, $2$, $6$]을 반환해야 한다.

제약 조건

• $p[0]=0$
• $0 \leq p[i] \leq l$이고 $p[i]$는 짝수이다. (모든 $0 \leq i \leq n-1$에 대해)
• $p[i] < p[i+1]$ (모든 $0 \leq i \leq n-2$에 대해)

서브태스크

1. (16점) $l = 100\;000$, $n = 2$, $q = 100\;001$
2. (21점) $l = 100\;000$, $n = 100$, $q = 100\;001$
3. (23점) $l = 100\;000$, $n = 2$, $q = 20$
4. (40점) $l = 100\;000$, $n = 1000$, $q = 20\;000$

또한 서브태스크 4는 부분 점수 서브태스크이다. 모든 테스트 케이스에서 호출한 use_detector의 횟수 중 최댓값을 $m$이라고 하자.

• $m \gt 20\;000$이면 $0$점을 받는다.
• $7500 \lt m \leq 20\;000$이면 $\frac{20\;000-m}{12\;500} \cdot 40$점을 받는다.
• $m \leq 7500$이면 $40$점을 받는다.

• $1$번째 줄: $\;\;l\;\;n\;\;q$
• $2$번째 줄: $\;\;p[0]\;\;p[1]\;\;\ldots\;\;p[n-1]$

샘플 그레이더는 다음 형식으로 답을 출력한다.

• $1$번째 줄: find_routers가 보고한 $\;\;p[0]\;\;p[1]\;\;\ldots\;\;p[n-1]$
• $2$번째 줄: use_detector의 호출 횟수.

샘플 그레이더는 다음 형식으로 입력을 읽는다.