Codeforces Round 864 (Div. 2) |
---|
Закончено |
Это интерактивная задача.
Li Ming и Li Hua играют в игру. У Li Hua есть шахматная доска размером $$$n\times m$$$. Обозначим $$$(r, c)$$$ ($$$1\le r\le n, 1\le c\le m$$$) как клетку в $$$r$$$-й строке сверху и в $$$c$$$-м столбце слева. Li Ming поставил короля на шахматную доску, и Li Hua нужно угадать его позицию.
Li Hua может задавать Li Ming не более $$$3$$$ вопросов. В каждом вопросе он может выбрать клетку и спросить минимальное количество шагов, необходимых для перемещения короля на выбранную клетку. Каждый вопрос является независимым, что означает, что король на самом деле не перемещается.
Король может переместиться из $$$(x,y)$$$ в $$$(x',y')$$$ тогда и только тогда, когда $$$\max\{|x-x'|,|y-y'|\}=1$$$ (как показано на следующем рисунке).
Позиция короля выбирается перед взаимодействием.
Предположим, что вы Li Hua. Пожалуйста, решите эту задачу.
Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^3$$$).
Первая строка каждого набора входных данных содержит два целых числа $$$n,m$$$ ($$$1\le n,m\le 10^9$$$) — размер шахматной доски, после чего начинается взаимодействие.
Чтобы задать вопрос, выведите «? $$$r$$$ $$$c$$$» (без кавычек, $$$1 \leq r \leq n, 1 \leq c \leq m$$$). Затем вы должны ввести ответ со стандартного ввода — минимальное количество шагов, необходимое королю для перемещения в выбранную клетку.
Если ваша программа задала некорректный вопрос или вы задали больше трёх вопросов, интерактор немедленно завершится, а ваша программа получит вердикт Неправильный ответ.
Чтобы дать окончательный ответ, выведите «! $$$r$$$ $$$c$$$» (без кавычек, $$$(r,c)$$$ - это начальная координата короля). Обратите внимание, что вывод ответа не учитывается в ограничение в $$$3$$$ вопроса.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Для взлома используйте следующий формат.
Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$).
Первая и единственная строка каждого набора входных данных должна содержать четыре целых числа $$$n,m,r,c$$$ ($$$1\le r\le n\le 10^9,1\le c\le m\le 10^9$$$).
2 3 4 1 2 5 3 3 1 2
? 2 3 ? 2 4 ! 2 2 ? 2 2 ? 5 2 ? 5 3 ! 5 1
В первом наборе входных данных король находится в точке $$$(2,2)$$$. Для перемещения в клетку $$$(2,3)$$$ требуется $$$1$$$ шаг, а для перемещения в клетку $$$(2,4)$$$ — $$$2$$$ шага.
Обратите внимание, что ваши запросы могут быть другими. Это просто пример запросов, которые вы можете сделать.
Название |
---|