KOI 2차 2020 고4- 경계 로봇 > 문제은행 : 정보올림피아드&알고리즘




4608 : 경계 로봇

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

비밀 연구소의 높은 장벽 앞에는 침입자를 식별할 수 있는 N개의 센서가 놓여 있다. 장벽은 일직선으로 뻗어있어서, 직선 상의 구간 [0, L]로 나타내고, 센서는 이 구간 안에 놓인 점으로 나타내자.

 

센서는 식별 범위 r를 가지며, 이 범위는 모든 센서에 대하여 동일하다. 다시 말해서, 점 p에 있는 센서는 구간 [p − r, p + r]에 속한 침입자를 식별할 수 있다. 이 구간을 센서의 식별 구간이라고 한다.

 

장벽의 경계를 담당하는 하나의 로봇이 존재하고, 이 로봇은 초기에 장벽의 왼쪽 끝에 위치한다. 로봇은 장벽을 따라 좌우로 움직이면서 센서를 실어서 옮길 수 있다. 로봇은 자기 위치에서만 센서를 실거나 놓을 수 있다. 그러나, 로봇이 한 번에 실을 수 있는 센서의 개수에는 제한이 없다.

 

모든 센서의 식별 구간의 합집합이 장벽 [0, L]을 완전히 포함한다면, 센서가 완벽한 경계에 있다고 한다. 로봇은 완벽한 경계를 위하여 필요하면 센서를 실어서 옮겨야 한다. 이때, 로봇이 움직인 총 거리를 최소화해야 한다.

 

장벽 [0, L]과 센서 N개의 초기 위치, 센서의 식별 범위 r이 주어질 때, 완벽한 경계를 위해서 로봇이 움직여야 하는 총 거리의 최솟값을 출력하는 프로그램을 작성하시오.


 


제약 조건


  • 1 ≤ N ≤ 1,000,000
  • 1 ≤ L ≤ 1012
  • 1 ≤ r ≤ 1012
  • L과 r은 모두 정수이다.
  • 모든 센서의 초기 위치는 0 이상 L 이하인 정수이다.
  • 모든 센서의 초기 위치는 단조증가하는 순서대로 주어진다.

 


부분문제


  • (12점) N ≤ 10, L ≤ 100, r ≤ 10
  • (7점) N ≤ 30, L ≤ 2,000, r ≤ 30
  • (12점) N ≤ 500
  • (28점) N ≤ 2,500
  • (41점) 추가 제약 조건 없음.

입력형식

첫 번째 줄에 각각 센서의 개수와 장벽의 길이, 센서의 식별 범위를 나타내는 세 정수 N, L, r이 공백을 사이에 두고 주어진다.

두 번째 줄에 센서들의 초기 위치를 나타내는 N개의 정수가 공백을 사이에 두고 단조증가하는 순서대로 주어진다. 즉, N개의 정수가 정렬된 상태로 주어진다.​ 


출력형식

만약 센서들을 어떻게 배치하더라도 완벽한 경계를 할 수 없다면, 첫 번째 줄에 −1을 출력한다.

만일 완벽한 경계가 가능하다면, 첫 번째 줄에 완벽한 경계를 위해 로봇이 움직여야 하는 총 거리의 최솟값을 출력한다. 이 값은 항상 정수임을 증명할 수 있다.​ 

 


입력 예

2 7 2
3 6

출력 예

4

입력 예

2 10 3
0 0

출력 예

7

입력 예

1 4 2
2

출력 예

0

입력 예

1 4 1
2

출력 예

-1

Hint!

참고

첫 번째 예제의 경우, 다음과 같이 로봇이 움직이는 것이 최적이다.

 

  1. 0에 위치한 로봇이 3으로 이동한다.
  2. 현 위치에 놓여 있는 센서를 싣는다.
  3. 3에 위치한 로봇이 2로 이동한다.
  4. 실은 센서를 현 위치에 놓는다.

 

이때, 센서의 최종 위치는 2, 6이며, 센서의 식별 구간의 합집합은 [0, 8]로, 장벽 [0, 7]을 완전하게 포함한다.

로봇이 움직인 총 거리는 4이며, 이보다 적게 움직여서 완벽한 경계를 할 수 없으므로, 답은 4이다.

두 번째 예제의 경우, 다음과 같이 로봇이 움직이는 것이 최적이다.

 

  1. 현 위치 0에 놓여 있는 센서 두 개를 모두 싣는다.
  2. 0에 위치한 로봇이 1.5로 이동한다.
  3. 실은 센서 중 하나를 현 위치에 놓는다.
  4. 1.5에 위치한 로봇이 7로 이동한다.
  5. 남은 센서 하나를 현 위치에 놓는다.

 

이와 같이, 로봇이 센서를 정수가 아닌 위치에 놓을 수 있음에 유의하라.

 ​ 




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP