온야오말레는 고속도로를 따라 설치된 가로등의 전구를 백열전구에서 더 에너지 효율적이고 밝은 LED 전구로 교체하는 프로젝트를 이끌고 있다. 그녀는 모든 오래된 백열전구를 이미 제거했으며, 이제 새 LED 전구를 설치하는 데 집중하고 있다. 새 전구가 더 밝기 때문에, 온야오말레는 일부 가로등이 필요 없을 수도 있고 이를 사용하지 않으면 에너지를 더 절약할 수 있다고 생각한다.

우리는 고속도로를 서쪽에서 동쪽으로 뻗은 길이 \mathbf{M}미터의 직선으로 모델링한다. x-번째 미터는 고속도로의 서쪽 끝에서 동쪽으로 x미터 떨어진 점이다. 만약 가로등이 x-번째 미터에 있고, 조명 반경이 \mathbf{R}미터인 전구를 설치하면, 그 가로등은 고속도로의 \max(0, x - \mathbf{R})-번째 미터에서 \min(\mathbf{M}, x + \mathbf{R})-번째 미터까지(양 끝 포함) 구간을 비춘다. 온야오말레는 고속도로의 모든 점이 적어도 하나의 전구에 의해 비춰지도록 전구를 설치해야 한다. 이는 고속도로 양 끝점에서 정수 미터 거리가 아닌 점들도 포함한다는 것에 유의하라. 전구가 설치되지 않은 가로등은 아무것도 비추지 않는다.

고속도로의 길이(미터) \mathbf{M}, 새 전구의 조명 반경(미터) \mathbf{R}, 그리고 모든 가로등의 위치가 주어졌을 때, 고속도로 전체를 비추기 위해 온야오말레가 설치해야 하는 전구의 최소 개수를 구하라. 불가능하다면 그 사실을 보고하라.

#10449 upload 1 done 1 how_to_reg 1

Illumination Optimization timer 10s memory 2048MB

#10449

Illumination Optimization 10s 2048MB