문제
게리(Gary)는 높이와 너비가 각각 정확히 2 × 109 나노미터인 큰 정사각형 벽을 가지고 있다. 게리는 벽에 다트판을 설치했다. 다트판은 원형이며, 반지름은 A 나노미터 이상 B 나노미터 이하(포함)이다. 다트판은 벽 안에 완전히 포함되어 있지만, 벽의 가장자리에 닿을 수는 있다. 다트판의 중심은 벽의 각 변으로부터 정수 나노미터만큼 떨어져 있다.
게리는 친구 미카(Mika)를 초대해 흥미로운 게임을 하기로 했다. 게리는 미카에게 눈가리개를 씌우고 다트판의 중심을 향해 다트를 던지라고 도전한다. 미카를 돕기 위해, 미카가 벽에 다트를 던질 때마다 게리는 그 다트가 다트판에 맞았는지 여부를 알려준다.
미카는 다트판이 벽의 어디에 있는지 모르지만, 다트를 매우 잘 던지기 때문에 나노미터 단위의 정밀도로 던질 수 있다. 즉, 벽의 각 변으로부터 정수 나노미터만큼 떨어진 임의의 점을 정확히 겨냥해 맞힐 수 있다. 매번 다트를 던진 직후 게리는 다트가 다트판의 중심을 맞혔는지, 중심이 아닌 다른 부분을 맞혔는지, 아니면 완전히 빗나가 벽의 빈 부분에 맞았는지를 알려준다.
300번을 초과해 다트를 던지지 않고 다트판의 중심을 맞히도록 미카를 도울 수 있겠는가?
출처
GCJ 2020r1b B
로그인해야 코드를 작성할 수 있어요.