BOJ 28595 Find the Box

문제 링크:

문제 내용

$H$행 $W$열의 사각 격자 어딘가에 상자가 하나 놓여 있습니다. 당신은 로봇을 움직여서 상자의 위치를 알아내야 합니다.

당신은 길이 $20\;000$ 이하의 <^>v로 이루어진 쿼리를 던질 수 있습니다. 그러면 로봇은 다음과 같이 움직인 뒤 최종 위치를 당신에게 알려 줍니다.

• 매 쿼리마다, 로봇은 $(0, 0)$에서 시작합니다. $(r, c)$는 $r$번째 행, $c$번째 열에 해당하는 칸을 의미합니다.
• 각각의 글자에 대해, <이면 왼쪽, ^이면 위쪽, >이면 오른쪽, v이면 아래쪽으로 한 칸 움직입니다. 이때 사각 격자의 밖으로 이동하려고 하거나 상자가 있는 칸으로 이동하려고 하게 되면 로봇은 그 글자를 무시하고 움직이지 않습니다.

인터랙션

먼저 인터랙터가 당신의 프로그램에게 $H$와 $W$의 값을 알려 줍니다. ($1 \le H, W \le 50$)

당신의 프로그램은 ? <query_string>의 형식으로 출력하여 인터랙터에게 쿼리를 할 수 있습니다. 쿼리를 한 후에는 반드시 flush를 해야 합니다.

그러면 인터랙터는 그 쿼리에 대해 로봇의 최종 위치 $(r, c)$를 $r$과 $c$의 순서로 알려 줍니다.

상자의 위치를 알아냈다면, 상자의 위치가 $(r, c)$일 때 ! r c의 형식으로 출력하고 프로그램을 종료해야 합니다. 이 출력은 쿼리 횟수에 포함되지 않습니다.

모든 테스트 케이스에서 올바른 상자의 위치를 찾았다면, 그 중에서 가장 많은 쿼리 횟수가 $q$일 때 $\min(\frac{100 \sqrt{2}}{\sqrt{q}}, 100)$의 점수를 받습니다. $q = 2$여야 만점을 받을 수 있습니다.

문제 풀이