findthebox
EGOI Day 1 Tasks
English (ISC)

Find the Box
Problem Name

Find the Box

Time Limit

1 second

Memory Limit

1 gigabyte

Maj is a robotics researcher who works at Lund University. She has learned about a valuable
treasure in the cellar of the university. The treasure is in a box located in an empty room deep
underground. Unfortunately, Maj cannot just go and look for the box. It is very dark in the cellar
and going there with a light would raise suspicion. Her only way to ﬁnd the treasure is to remotely
control a robot vacuum cleaner that inhabits the cellar.
The cellar is represented as an H × W grid, where the rows are numbered from 0 to H − 1 (top tobottom) and the columns are numbered from 0 to W − 1 (left to right), meaning that 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, other than the cell (0, 0). Every night, the robot vacuum cleaner starts in the top left
corner and moves around the cellar.
Each night, Maj can give the robot a sequence of instructions on how it should move in the form ofa string consisting of characters “<”, “>”, “^” and “v”. Formally, if the robot is standing on cell (r, c)that is unblocked on all sides, “<” moves the robot left to cell (r, c − 1), “>” moves the robot right tocell (r, c + 1), “^” moves the robot up to cell (r − 1, c), and “v” moves the robot down to cell(r + 1, c).
The cellar walls are solid, so if the robot attempts to move outside the grid, nothing will happen.
The box is also solid, and cannot be pushed. At the end of each night, the robot will report its
location, and go back to the top left corner.
Time is of the essence, so Maj decides to ﬁnd the box in as few nights as possible.

Interaction
This is an interactive problem.
Your program should start by reading a line with two integers H and W : the height andwidth of the grid.

findthebox (1 of 4)

Then, your program should interact with the grader. In each round of interaction, you should
print a question mark “?”, followed by a non-empty string s consisting of characters “<”, “>”,“^”, “v”. The length of this string can be at most 20 000. Then, your program should read twointegers r, c (0 ≤ r ≤ H − 1, 0 ≤ c ≤ W − 1), the location of the robot after executing theinstructions. Note that the robot always goes back to (0, 0) after each query.
When you know the location of the box, print “!” followed by the two integers rb , cb , the row
and column of the box (0 ≤ rb ≤ H − 1, 0 ≤ cb ≤ W − 1). After this, your program must exitwithout making any further queries. This ﬁnal output does not count as a query whendetermining your score.
Make sure to ﬂush standard output after issuing a query, or else your program might get judged
as Time Limit Exceeded. In Python, print() ﬂushes automatically. In C++, cout << endl; also
ﬂushes in addition to printing a newline; if using printf, use fflush(stdout).
The grader is non-adaptive, meaning that the position of the box is determined before theinteraction begins.

Constraints and Scoring1 ≤ H, W ≤ 50.
The box will never be located at (0, 0). This means that H + W ≥ 3.
Each query can consist of at most 20 000 instructions.
You can issue at most 2 500 queries (printing the ﬁnal answer does not count as a query).
Your solution will be tested on a number of test cases. If your solution fails on any of these test
cases (e.g. by reporting the wrong box position (Wrong Answer), crashing (Runtime Error),exceeding the time limit (Time Limit Exceeded), etc.), you will receive 0 points and the appropriate
verdict.
If your program successfully ﬁnds the position of the box in all test cases, you will get the verdict
Accepted, and a score calculated as follows:score = min ( 100√2 , 100) points,√Q
where Q is the maximum number of queries used on any test case. Printing the ﬁnal answer does
not count as a query. The score will be rounded to the nearest integer.
In particular, to receive 100 points, your program must solve every test case using at most Q = 2queries. The table below shows some values of Q and the associated score.

Q

23

4

5...

20...

50...

2500

Score

1008271

63...

32...

20

...

3

findthebox (2 of 4)

Testing Tool
To facilitate the testing of your solution, we provide a simple tool that you can download. See“attachments” at the bottom of the Kattis problem page. The tool is optional to use, and you areallowed to change it. Note that the oﬃcial grader program on Kattis is diﬀerent from the testingtool.
Example usage (with H = 4, W = 5, and the hidden box at position r = 2, c = 3):
For Python programs, say solution.py (normally run as pypy3 solution.py):
python3 testing_tool.py pypy3 solution.py <<<"4 5 2 3"
For C++ programs, ﬁrst compile it (e.g. with g++-g-O2-std=gnu++17-staticsolution.cpp -o solution.out) and then run:python3 testing_tool.py ./solution.out <<<"4 5 2 3"

ExampleConsider the sample test case. The grid has height H = 4 and width W = 5, and the box is atposition (r, c) = (2, 3). The ﬁgure below shows the robot”s path when following the instructions of
the ﬁrst query “?

vv>>>>>><^^^^^>”, which results in the robot ending up at position(r, c) = (0, 2). Before the second query, the robot will go back to the top left corner (0, 0) again.
Then the solution issues another query “? >>>>>>>>vvvvvvvvvv” for which the robot ends up in
the bottom right corner (r, c) = (3, 4). Now the solution decides to guess the answer, by writing “!
2 3”, which is the correct position of the box.

findthebox (3 of 4)

grader output

your output

45? vv>>>>>><^^^^^>
02? >>>>>>>>vvvvvvvvvv
34!23

findthebox (4 of 4)