Background

Day 1 Problem C.

Translated from EGOI2023 findthebox.

Problem Description

This is an interactive I/O problem.

Mai is a robotics researcher working at Lund University. She learned that there is a priceless treasure hidden in the university basement. The treasure is inside a box in an empty room deep underground. Unfortunately, Mai cannot go and find the box directly. The basement is very dark, and bringing a lamp would look suspicious. The only way she can find the treasure is by remotely controlling a robot vacuum cleaner that lives in the cellar.

The basement is a $H\times W$ grid. Rows are numbered from $0$ to $H-1$ (top to bottom), and columns are numbered from $0$ to $W-1$ (left to right). That is, the top-left cell is $(0,0)$ and the bottom-right cell is $(H-1,W-1)$. The box with the treasure is in some unknown cell different from $(0,0)$. Every night, the robot vacuum starts moving in the basement from the top-left cell.

Each night, Mai gives the robot a sequence of commands to guide its movement. A command sequence is a string consisting of the characters <, >, ^, and v. Formally, if the robot is at cell $(r,c)$ and the corresponding direction is not blocked, < moves the robot left to $(r,c-1)$, > moves it right to $(r,c+1)$, ^ moves it up to $(r-1,c)$, and v moves it down to $(r+1,c)$.

The basement walls are very solid, so if the robot tries to move outside the grid, nothing happens. The box is also very solid and cannot be pushed. At the end of each night, the robot reports its position and returns to the top-left cell.

Time is money, so Mai needs to find the box in as few nights as possible.

Output Format

This is an interactive I/O problem.

• At the start, your program should read one line with two integers $H,W$, the height and width of the grid.
• After that, your program interacts with the interactor. In each interaction round, you should output a question mark ? followed by a non-empty string $s$ consisting of the characters <, >, ^, and v. The length of the string must be at most $2\times10^4$. Then, your program reads two integers $r,c$ ($0\le r\le H-1$, $0\le c\le W-1$), which is the robot's position after executing the commands. Note that after each query, the robot always returns to $(0,0)$.
• When you know the box position, output ! and two integers $r_b,c_b$ ($0\le r_b\le H-1$, $0\le c_b\le W-1$), the coordinates of the box. After this, your program must not make any more queries and must exit. This final output is not counted in the number of queries when computing your score.

Make sure to flush the output stream after each query, otherwise your program may get judged TLE. In Python, print() flushes automatically. In C++, cout << endl; flushes after printing a newline; if you use printf, use fflush(stdout).

The interactor is not adaptive, meaning the box position is fixed before the interaction begins.

4 5

0 2

3 4

? vv>>>>>><^^^^^>

? >>>>>>>>vvvvvvvvvv

! 2 3

Hint

Sample explanation.

Consider the sample. The grid has height $H=4$ and width $W=5$, and the box is at $(r,c)=(2,3)$. The figure below shows the robot's path after receiving the command ? vv>>>>>><^^^^^>, and the robot finally stops at $(r,c)=(0,2)$. Before the second query, the robot returns to the top-left cell $(0,0)$. The program asks ? >>>>>>>>vvvvvvvvvv, and the robot finally stops at the bottom-right cell $(r,c)=(3,4)$. Now the program decides to guess the answer and outputs ! 2 3, and, surprisingly, this is exactly the correct box position.

---

Constraints.

For all data, $1\le H,W\le 50$, the box will not be at $(0,0)$ (this means $H+W\ge 3$), each query contains at most $2\times 10^4$ commands, and you may make at most $2500$ queries (outputting the final answer is not counted as a query).

Your program will be tested on a certain number of test points. If your program fails on any test point (for example: outputs the wrong box coordinates (WA), crashes (RE), exceeds the time limit (TLE), etc.), you will get $0$ points and an appropriate verdict.

If your program successfully finds the box on all test points, you will get AC (translator's note: on Luogu, anything less than full score is treated as WA). The score is determined by the formula:

$$\textrm{score}=\min\left(\frac{100\sqrt{2}}{\sqrt{Q}},100\right)\textrm{ points}$$

where $Q$ is the maximum number of queries among all test points. Outputting the final answer is not counted as a query. The score is rounded to the nearest integer.

In particular, to get $100$ points, your program must solve all test points within $Q=2$ queries. The table below shows some values of $Q$ and their scores.

$Q$	$2$	$3$	$4$	$5$	$\cdots$	$20$	$\cdots$	$50$	$\cdots$	$2500$
Score	$100$	$82$	$71$	$63$	$\cdots$	$32$	$\cdots$	$20$	$\cdots$	$3$

Translated by ChatGPT 5