Problem B
Worm Worries
Languages
de
en
et
is
lt
lv
no
pl
ru
sv
You are looking for a place in the soil to put your pet
worm, Maximus. You limit your search to a box-shaped region
with dimensions
Maximus loves humid places, so you need to put him in a cell
which is at least as humid as its neighboring cells, otherwise
he goes away and you will have trouble finding him. In other
words, you need to place Maximus in a local maximum. More
precisely, you need to find a cell
where a value is treated as
However, the number of cells can be very large, so you do not want to measure the humidity of all the cells. Therefore, in this task, you are allowed to interact with the grader, and ask for the humidity at given points. When you have found a suitable location for Maximus, give that location to the grader.
Interactivity
The first line of the input contains four positive integers:
After that, you can write at most
After all these lines, your program must write out exactly
one line of the form “! x y z” and
terminate. This claims that the point
All values of
You must make sure to flush standard output before reading the grader’s response, or else your program will get judged as Time Limit Exceeded. This works as follows in the supported languages:
-
Java: System.out.println() flushes automatically.
-
Python: print() flushes automatically.
-
C++: cout << endl; flushes, in addition to writing a newline. If using printf, fflush(stdout).
-
Pascal: Flush(Output).
To help deal with this interaction, we provide optional helper code which you may copy into your program. A link to this code for all supported languages (C++, Pascal, Java, Python) can be found in the sidebar of the Kattis problem page. The helper code also uses fast input/output routines, which may be useful for Python and Java (only relevant for the last two test groups).
The grader will be non-adaptive; that is, each test case will have a fixed set of humidity values that do not depend on what measurements are performed by the program.
Constraints
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
Group |
Points |
Limits |
1 |
10 |
|
2 |
22 |
|
3 |
12 |
|
4 |
19 |
|
5 |
14 |
|
6 |
23 |
|
Sample dialogue
In Kattis there is one sample test case. In this sample, the
box has dimensions
As
JUDGE: 3 1 1 3 YOU: ? 3 1 1 JUDGE: 13 YOU: ? 2 1 1 JUDGE: 14 YOU: ? 1 1 1 JUDGE: 10 YOU: ! 2 1 1