Yet Another Contest 6 P3 - No More Cell Phone Messaging

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Recently, Josh and Mike have been chatting too much on cell phones instead of studying! Their parents are upset and wish to end this chatting immediately.

So that they are not disturbed by their parents, Josh and Mike are in hiding places! Josh is located at position (A, B), whilst Mike is located at position (C, D). It is known that 1 \le A, C \le N, 1 \le B, D \le M, and A, B, C, D are all integers. Furthermore, Josh is not at the same position as Mike, i.e., (A, B) \ne (C, D).

Their parents have a method to find Josh and Mike. They can stand at any position (X, Y), where 1 \le X \le N, 1 \le Y \le M, and X, Y are both integers. Then, based on the loudness of Josh and Mike's voices at that position, they can determine the minimum of the Manhattan distances to Josh and Mike. In other words, they can figure out the value of \min(|X-A|+|Y-B|, |X-C|+|Y-D|).

Can you help the parents find Josh and Mike by standing in no more than 5 positions?


1 \le N, M \le 10^9

Subtask 1 [25%]

M = 1

Subtask 2 [75%]

No additional constraints.


This is an interactive problem, where the interactor is not adaptive.

First, you should read in the values of N and M, which are space-separated on a single line.

Then, you should begin making queries. To make a query, output a line in the form ? X Y, representing the position where the parents will stand. You should then read in an integer on the following line, which will be equal to \min(|X-A|+|Y-B|, |X-C|+|Y-D|).

Finally, once you have made all of your queries, you should output a line in the form ! A B C D, representing your guesses of Josh and Mike's coordinates. Note that the order in which the two positions are outputted does not matter, that is, you may output Josh's and Mike's coordinates in either order.

If at any point you make an invalid query, or make more than 5 queries, the interactor will respond with -1 on the following line. Upon reading this value, you should terminate your program to receive a Wrong Answer verdict. Otherwise, you may receive an arbitrary verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

2 3
>>> ? 1 1
>>> ? 2 1
>>> ! 1 3 2 3


Josh is at position (1, 3) and Mike is at position (2, 3).

When the parents stand at (1, 1), they figure out that \min(|1-A|+|1-B|, |1-C|+|1-D|) = 2.

When the parents stand at (2, 1), they figure out that \min(|2-A|+|1-B|, |2-C|+|1-D|) = 2.

The parents have enough information to determine that Josh is at position (1, 3) and Mike is at position (2, 3), or vice versa. Note that ! 2 3 1 3 would also be a correct output, since the order in which Josh and Mike's coordinates are outputted does not matter.


There are no comments at the moment.