18446번 - 우체국 5 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 (추가 시간 없음) | 1024 MB | 204 | 30 | 12 | 33.333% |
문제
원형으로 큰 길(순환로)이 뻗어 있고, 길 옆으로 V개의 마을이 자리잡고 있다. 큰 길의 둘레 길이는 정수 L이다. 이 문제에서 큰 길은 0 이상 L-1 이하의 정수가 늘어져 있는 원이고, 각 마을의 위치는 길 상의 정수 좌표로 표현된다. 한 위치에 여러 마을이 있을 수 있다. 좌표가 x, y인 두 마을의 거리는 min(|x - y|, L - |x - y|) 이다.
우리는 이들 마을이 있는 곳에 우체국을 P개 지으려고 한다. 물론 모든 마을마다 다 짓는 건 아니다. 전체 마을 중 몇 곳을 골라, 그 위치에 우체국을 짓게 된다. 우리는 그 때 각 마을과 그 마을과 가장 가까운 우체국 사이의 거리의 합이 최소가 되게 하고 싶다.
각 마을의 위치와 짓고자 하는 우체국 개수를 입력받아서, 각 마을과 그 마을과 가장 가까운 우체국 사이 거리의 합으로 있을 수 있는 최소값을 계산하고, 그런 결과를 낼 수 있도록 각 우체국을 지을 위치를 출력하는 프로그램을 작성하라.
입력
첫 줄에는 세 정수 V, P, L이 주어진다. (1 ≤ P ≤ V ≤ 250 000, 1 ≤ L ≤ 1012)
다음 줄에는 각 마을의 위치를 나타내는 V개의 정수 좌표가 나온다. 좌표는 비내림차순으로 정렬되어 있다. 각 좌표의 범위는 0 이상 L-1 이하이다.
출력
첫째 줄에는, 각 마을과 거기서 가장 가까운 우체국 사이 거리들의 합의 최소값을 나타내는 정수 S를 출력한다.
다음 줄에는, 우체국을 지을 마을들을 골라, 그 마을의 위치를 나타내는 P개의 정수를 비내림차순으로 출력한다.
예제 입력 1
10 5 200 1 2 3 6 7 9 11 22 44 50
예제 출력 1
9 2 7 22 44 50
예제 입력 2
10 5 51 1 2 3 6 7 9 11 22 44 50
예제 출력 2
8 1 6 9 22 44
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호