CF1797C.Li Hua and Chess
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is an interactive problem.
Li Ming and Li Hua are playing a game. Li Hua has a chessboard of size n×m . Denote (r,c) ( 1≤r≤n,1≤c≤m ) as the cell on the r -th row from the top and on the c -th column from the left. Li Ming put a king on the chessboard and Li Hua needs to guess its position.
Li Hua can ask Li Ming no more than 3 questions. In each question, he can choose a cell and ask the minimum steps needed to move the king to the chosen cell. Each question is independent, which means the king doesn't actually move.
A king can move from (x,y) to (x′,y′) if and only if max{∣x−x′∣,∣y−y′∣}=1 (shown in the following picture).
The position of the king is chosen before the interaction.
Suppose you were Li Hua, please solve this problem.
输入格式
无
输出格式
The first line contains the number of test cases t ( 1≤t≤103 ).
The first line of each test case contains two integers n,m ( 1≤n,m≤109 ) — the size of the chessboard, and then the interaction begins.
To ask a question, print "? r c " (without quotes, 1≤r≤n,1≤c≤m ). Then you should input the response from standard input — the minimum steps the king needs to move to the chosen cell.
If your program has asked an invalid question or has run out of questions, the interactor will terminate immediately and your program will get a verdict Wrong answer.
To give the final answer, print "! r c " (without the quotes, (r,c) is the king's initial coordinate). Note that giving this answer is not counted towards the limit of 3 questions.
After asking a question do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hacks
To hack, use the following format.
The first line should contain a single integer t ( 1≤t≤103 ).
The first and only line of each test case should contain four integers n,m,r,c ( 1≤r≤n≤109,1≤c≤m≤109 ).
输入输出样例
输入#1
2 3 4 1 2 5 3 3 1 2
输出#1
? 2 3 ? 2 4 ! 2 2 ? 2 2 ? 5 2 ? 5 3 ! 5 1
说明/提示
In test case 1, the king is at (2,2) . It takes 1 step to move to (2,3) and 2 steps to move to (2,4) .
Note that the questions may not seem sensible. They are just a sample of questions you may ask.