로봇(robot) > 문제은행



문제은행

3429 : 로봇(robot)

제한시간: 1Sec    메모리제한: 1024mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



N개의 로봇들이 원 상에 놓여있다.

원 상의 위치는 가장 북쪽을 위치 0으로 하고 일정한 간격으로 원을 M (≥ N​) 등분해서 

나뉘는 지점에 시계방향으로 순서대로 위치 1부터 M-1을 부여한다. 

그러면 원 상의 위치 0부터 M-1이 정의된다(그림1). 로봇들은 초기에 서로 다른 N개의 위치에 놓여있다.

 

원 상에 두 위치 xy사이의 거리는 y - x (y ≥ x)로 정의한다. 

로봇 Ri가 위치 xi에 놓여있으면 로봇은 자신으로부터 반시계방향과 시계방향으로 일정한 범위 R > 0안의 점들을 감시할 수 있다. 

다시 말해서, 위치 xi에서 시계 반대방향으로 거리 R 떨어진 위치를 a라 하고, 

시계 방향으로 거리 R 떨어진 위치를 b라고 할 때, 로봇 Ri는 원 상의 시계방향으로 위치 a에서 b사이의 부분을 감시할 수 있다.

 

우리는 원의 모든 부분을 감시하고 싶다. 초기 로봇들의 위치에서 감시하지 못하는 부분이 있을 수 있으므로 

이런 경우에 우리는 로봇들을 이동해서 원의 모든 부분을 감시할 수 있도록 하고 싶다. 

우리는 M ≤ 2RN 을 가정함으로써 항상 원의 모든 부분을 감시할 수 있는 로봇들의 이동을 찾을 수 있다.

 

로봇들은 이동하는 경우 위에 정의된 원 상의 위치로만 이동할 수 있고, 각 로봇마다 많아야 한번만 이동할 수 있다. 

이 때, 로봇들이 이동한 거리의 최댓값을 최소화하려고 한다.

 

예를 들어, 아래 <그림 1>에서 3개 로봇 R1, R2, R3 가 각각 위치 1, 2, 5에 놓여있고 감시 범위 R = 2이다. 

원의 모든 부분을 감시하기 위해서 로봇 R1​은 위치 0으로 로봇 R3​는 위치 6으로 이동한다. 

이것이 로봇들의 이동 거리의 최댓값이 최소가 되는 이동이다.

 

592d7a7e0c8d86d1da5cb1fdc052ff77_1563674
 

 

N개 로봇들의 위치, 범위 R, 정수 이 주어질 때, 

원의 모든 부분을 감시할 수 있도록 로봇들을 이동할 때, 최대 이동거리의 최솟값을 찾아서 출력하시오.​

 


표준 입력으로 다음 정보가 주어진다. 입력의 첫 줄에는 로봇들의 개수를 나타내는 정수  ( 1 ≤ N ≤ 1,000,000) 이 주어진다. 
둘째 줄에는 로봇의 감시 범위와 원 상의 위치를 정의하는 두 정수  R  M(1 ≤ R,M ≤ 109, N ≤ M ≤ 2RN)이 주어진다.
다음줄에 초기 로봇의 위치를 나타내는 서로 다른 N개의 정수 xi(0 ≤ xi ≤ M-1, i=1, ..., N)가 공백을 사이에 두고 주어진다.

[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 10점에 해당하며  M ≤ 10 이다. 
* 부분문제 2: 전체 점수 100점 중 30점에 해당하며  M ≤ 7,000 이다. 
* 부분문제 3: 전체 점수 100점 중 60점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.


표준 출력으로 원의 모든 부분을 감시할 수 있도록 로봇들의 최대 이동 거리의 최솟값을 출력한다.

[Copy]
3
2 10
1 2 5
[Copy]
1


[Copy]
6
1 11
0 1 2 3 4 5
[Copy]
2






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.