1797C.md (2730B)
1 Source: https://codeforces.com/problemset/problem/1797/C 2 3 C. Li Hua and Chess 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is an interactive problem. 22 23 Li Ming and Li Hua are playing a game. Li Hua has a chessboard of size $n\times m$. Denote $(r, c)$ ($1\le r\le n, 1\le c\le 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. 24 25 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. 26 27 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). 28 29 | | 30 | --- | 31 | | 32 33 The position of the king is chosen before the interaction. 34 35 Suppose you were Li Hua, please solve this problem. 36 37 Interaction 38 39 The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). 40 41 The first line of each test case contains two integers $n,m$ ($1\le n,m\le 10^9$) — the size of the chessboard, and then the interaction begins. 42 43 To ask a question, print "? $r$ $c$" (without quotes, $1 \leq r \leq n, 1 \leq c \leq m$). Then you should input the response from standard input — the minimum steps the king needs to move to the chosen cell. 44 45 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. 46 47 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. 48 49 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: 50 51 * fflush(stdout) or cout.flush() in C++; 52 * System.out.flush() in Java; 53 * flush(output) in Pascal; 54 * stdout.flush() in Python; 55 * see the documentation for other languages. 56 57 Hacks 58 59 To hack, use the following format. 60 61 The first line should contain a single integer $t$ ($1 \le t \le 10^3$). 62 63 The first and only line of each test case should contain four integers $n,m,r,c$ ($1\le r\le n\le 10^9,1\le c\le m\le 10^9$). 64 65 Example 66 67 Input 68 69 ``` 70 2 71 3 4 72 73 1 74 75 2 76 77 5 3 78 79 3 80 81 1 82 83 2 84 ``` 85 86 Output 87 88 ``` 89 ? 2 3 90 91 ? 2 4 92 93 ! 2 2 94 95 ? 2 2 96 97 ? 5 2 98 99 ? 5 3 100 101 ! 5 1 102 ``` 103 104 Note 105 106 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)$. 107 108 | | 109 | --- | 110 | | 111 112 Note that the questions may not seem sensible. They are just a sample of questions you may ask.