전파 망원경 설치
골드 III의견: 0
천문대가 둘레 \(L\) 인 원형 능선 도로 위에 전파 망원경을 설치하려 한다. 도로를 따라 잰 위치 좌표(원점에서 시계 방향으로 잰 거리) 후보가 서로 다른 \(N\) 곳 \(x_1, \dots, x_N\) 으로 주어진다. 이 중 정확히 \(C\) 곳에 망원경을 설치한다.
두 망원경 사이의 거리는 원을 따라 잰 거리(시계 방향과 반시계 방향 중 더 짧은 쪽)로 정의한다. 인접 간섭을 줄이기 위해, 설치한 망원경들 중 가장 가까운 두 망원경 사이의 원형 거리 가 최대가 되도록 설치하려 한다.
이때 얻을 수 있는 최대 가능한 최소 간격 을 구하여라.
\(2 \le C \le N \le 2{,}000\), \(C \le L \le 10^9\), \(0 \le x_i < L\). 좌표는 모두 서로 다르다.
첫째 줄에 후보 좌표의 수 \(N\), 설치할 망원경 수 \(C\), 도로의 둘레 \(L\) 이 주어진다. (\(2 \le C \le N \le 2{,}000\), \(C \le L \le 10^9\))
다음 \(N\) 개의 줄에 각각 좌표 \(x_i\) 가 주어진다. (\(0 \le x_i < L\), 모든 좌표는 서로 다르다.)
설치한 망원경 중 가장 가까운 두 망원경 사이의 원형 거리의 최댓값을 한 줄에 출력한다.
4 2 10
0
3
5
8
5둘레 10 인 원에서 좌표 0 과 5 를 고르면 두 방향 거리가 모두 5 로 최소 간격 5 를 얻으며, 이것이 가능한 최댓값이다.
6 3 12
0
2
4
6
8
10
4둘레 12 인 원에서 좌표 0, 4, 8 을 고르면 인접 간격이 모두 4 로 균등해 최소 간격 4 가 최대이다.
riseoj 작성
출처 Original
평가 및 의견
전파 망원경 설치
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
전파 망원경 설치