행성 탐사 차량인 Tycho VIII은 광물 샘플을 수집한 후 기지로 돌아가야 합니다. Tycho는 위치 0에서 출발하여 기지 위치인 b로 직선 경로로 이동합니다. 이동하는 동안 Tycho는 초당 1 단위의 느리지만 꾸준한 속도로 이동합니다. 매 초마다, Tycho는 혹독한 행성 환경으로 인해 1 단위의 환경 피해를 입습니다.

상황은 근처의 펄서로 인한 방사선 때문에 더 악화됩니다. 펄서는 매 p초마다 d 단위의 추가적인 피해를 줍니다. 그러나 이 방사선 피해는 경로상의 n개의 피난처(동굴, 식물, 큰 바위, 행성의 거대 동물들의 시체 등)에 숨음으로써 피할 수 있습니다. Tycho는 어느 지점에서든지 원하는 시간만큼 멈출 수 있습니다.

시작 위치 0과 기지 위치 b는 둘 다 피난처가 있어 그곳에서는 방사선 피해를 받지 않습니다.

Tycho가 기지로 돌아가는 동안 받는 최소 피해는 얼마일까요?

예를 들어, 기지 위치가 18이고 피난처가 8번과 15번 위치에 있다고 가정합시다.

펄서의 주기는 4초라고 가정합니다. 즉, 피난처가 없는 Tycho는 4초, 8초, 12초 등에서 피해를 받습니다. Tycho가 시작 위치(피난처가 있는 곳)에서 0초에 출발하면, 첫 번째 피난처에 도달하는 데 8초가 걸리며, 이때 4초에 방사선 피해 d를 입습니다(하지만 8초에는 그곳에서 피난처가 있기 때문에 피해를 받지 않습니다). 계속해서 멈추지 않고 기지에 도달하면, 18초에 기지에 도달하면서 12초와 16초에 각각 d의 방사선 피해를 입게 됩니다. 이렇게 되면 방사선 피해는 d + d = 2d이고, 환경 피해는 18이 됩니다. 총 피해는 2d + 18입니다.

대신, Tycho가 두 번째 피난처(15번 위치)에서 1초를 기다리면, 16초에 발생하는 펄서의 방사선 피해를 받지 않게 되며, 기지에 19초에 도달하여 총 피해는 2d + 19가 됩니다. 이는 d가 어떤 값이든 더 유리한 경우입니다. 두 가지 상황은 다음과 같습니다:

만약 펄서의 주기가 10초라면, Tycho는 시작 위치에서 2초를 기다린 후, 피난처에 멈추지 않고 바로 기지로 돌아갈 수 있습니다. 이렇게 하면 첫 번째 피난처(8번 위치)를 정확히 펄서가 폭발하는 순간에 지나가게 되어, 기지에는 20초에 도달하고, 총 피해는 20의 환경 피해만 입고 방사선 피해는 전혀 받지 않게 됩니다.

#8199 upload - done - how_to_reg - call_split Subtask

Tycho timer 2s memory 1024MB

#8199
Subtask

Tycho 2s 1024MB