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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

로봇(robot) timer 1s memory 1024MB

로봇(robot) 1s 1024MB