codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.