보물찾기

이 문제는 인터랙티브 점수제 문제이다.

? x y 쿼리는 현재 남아 있는 보물상자와의 가장 가까운 맨해튼 거리를 알려준다. ! x y 쿼리로 보물상자를 하나 찾으면 해당 보물상자는 사라지므로, 이후 ? 쿼리의 응답은 남아 있는 보물상자들만을 기준으로 계산된다.

가장 단순한 방법은 모든 칸에 대해 ? x y를 수행하고, 응답이 $0$인 칸을 ! x y로 보고하는 것이다. 이 방법은 최대 $10000$번의 ? 쿼리를 사용한다.

높은 점수를 받기 위해서는 거리 정보가 한 번에 많은 칸을 배제한다는 점을 이용해야 한다. 예를 들어 어떤 칸 $(x,y)$에서 응답이 $d$라면, 현재 남아 있는 보물상자 중 적어도 하나는 $(x,y)$로부터 거리 $d$인 마름모 위에 있으며, 거리 $d-1$ 이하인 모든 칸에는 보물상자가 없다.

이 문제의 인터랙터는 일부 적응형이다. 인터랙터는 처음부터 하나의 보물 배치만 고정하지 않고, 여러 가능한 보물 배치를 후보로 유지한다. 참가자 프로그램의 쿼리에 대해 가능한 후보가 최대한 많이 남도록 응답을 선택할 수 있다. 따라서 특정 고정 데이터에만 맞춘 풀이, 랜덤 추측 풀이, 제한된 패턴만 가정하는 풀이는 높은 점수를 받기 어렵다.