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

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

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

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

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

#4608 upload 7 done - how_to_reg - call_split Subtarea

경계 로봇 timer 1s memory 256MB

#4608
Subtarea

경계 로봇 1s 256MB