19931번 - Finding Routers 서브태스크다국어언어 제한함수 구현

문제

There is a street of length $l$ meters stretching from left to right, with $n$ small routers occupying various distinct positions along it. The origin is defined to be the leftmost point of the street. The routers are labelled 0ドル$ to $n-1$ from left to right, and router $i$ is placed $p[i]$ meters away from the origin.

It is guaranteed that router 0ドル$ is at the origin, and the distance in meters from each router to the origin is an even integer.

You wish to find out the position of each of the $n$ routers. As the routers are very small and difficult to spot from afar, you've decided to use the following procedure to find them:

• Place a detector on a spot that is $x$ meters away from the origin,
• Use the detector to find the label of the router closest to it. If there are two routers that are the same distance away from it, it will respond with the router with the smaller label.

You are allowed to use the detector at most $q$ times. Devise a strategy to find the positions of all the routers.

구현

You should implement the following procedure:

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

• $l$: length of the street in meters.
• $n$: number of routers.
• $q$: maximum number of times the detector can be used.
• This procedure will be called exactly once by the grader.
• It should return an array $p$ indicating the positions of each router, with $p[i]$ being the distance between router $x$ and the origin.

The above procedure can make calls to the following procedure:

int use_detector(int x)

• $x$: distance between the detector and the origin.
• $x$ must be at least 0ドル$ and at most $l$.
• This procedure will return the label of the router closest to the detector. If there are two routers that are the same distance away from it, it will return the smaller label.
• This procedure may be called no more than $q$ times.

입력

출력

제한

• $p[0]=0$
• 0ドル \leq p[i] \leq l$ and $p[i]$ is even. (for all 0ドル \leq i \leq n-1$)
• $p[i] < p[i+1]$ (for all 0ドル \leq i \leq n-2$)

예시 1

Consider the following call:

find_routers(5, 2, 10)

There are 2ドル$ routers on a street of length 5ドル$ meters and you are allowed at most 10ドル$ calls to use_detector. Suppose the routers are placed at 0ドル$ and 4ドル$ meters away from the origin respectively.

The find_routers procedure may choose to call use_detector(3), which returns 1ドル,ドル as router 1ドル$ at position 4ドル$ is closest to the detector.

The find_routers procedure may then choose to call use_detector(2), which returns 0ドル,ドル as both routers 0ドル$ and 1ドル$ are the same distance away from the detector and router 0ドル$ has a smaller label.

At this point, there is sufficient information to conclude that the routers are at positions 0ドル$ and 4ドル$ respectively.

As such, the find_routers procedure should return [0ドル,ドル 4ドル$].

예시 2

Consider the following call:

find_routers(6, 3, 10)

There are 3ドル$ routers on a street of length 6ドル$ meters and you are allowed at most 10ドル$ calls to use_detector. Suppose the routers are placed at 0ドル,ドル 2ドル$ and 6ドル$ meters away from the origin respectively.

The find_routers procedure may choose to call use_detector(5), which returns 2ドル$ as router 2ドル$ is at position 6ドル$ and therefore is the closest to the detector.

The find_routers procedure may then choose to call use_detector(4), which returns 1ドル,ドル as routers 1ドル$ and 2ドル$ are an equal distance away from the detector.

At this point, there is sufficient information to conclude that the routers are at positions 0ドル,ドル 2ドル$ and 6ドル$ respectively.

As such, the find_routers procedure should return [0ドル,ドル 2ドル,ドル 6ドル$].

서브태스크

힌트

첨부

• routers.zip