[고등부] 2024 KOI 2차대회 대비 모의고사 (3주차)

정올이는 하나의 로봇과 원형의 둘레가 L인 원 위에 각각 점 0에 위치해 있다 (1 ≤ L ≤ 10^9).

정올이는 원을 따라 시계방향 또는 반시계방향으로 초당 1단위씩 이동할 수 있다. 이 문제에서 모든 움직임은 연속적이다.

정올이는 초기 로봇과 추가적인 R-1개의 로봇을 균형있게 배치하고 싶다.

균형있게 배치되었다는 것은 배치를 마친 순간 각각의 인접한 로봇 사이의 거리가 L/R이 되어야 한다는 것이다 (2 ≤ R ≤ 20, R은 L을 나눌 수 있다).

단, 정올이가 로봇을 배치할 수 있는 지점은 총 N개 있으며 (1 ≤ N ≤ 10^5), 각각의 지점 i는 0으로부터 시계 반대방향으로 a_i의 거리에 있다 (0 ≤ a_i < L).

현재 정올이가 로봇을 배치할 수 있는 지점에 있으면 즉시 그 곳에 로봇을 배치할 수 있다.

모든 로봇 (초기 로봇 포함)은 시계 반대방향으로 K초마다 1단위를 이동하는 비율로 지속적으로 이동한다 (1 ≤ K ≤ 10^6).

정올이가 모든 로봇을 균형있게 배치하는 데 필요한 최소 시간을 계산하는 프로그램을 작성하시오.