| Codeforces Round 931 (Div. 2) |
|---|
| Закончено |
Это интерактивная задача.
Вам дано клетчатое поле из $$$n$$$ строк и $$$m$$$ столбцов. Координаты $$$(x, y)$$$ обозначают клетку на поле, где $$$x$$$ ($$$1 \leq x \leq n$$$) — номер строки, начиная сверху, и $$$y$$$ ($$$1 \leq y \leq m$$$) — номер столбца, начиная слева. Гарантируется, что на поле ровно $$$2$$$ мины в различных клетках, обозначенных $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$. Вы можете сделать не более $$$4$$$ запросов к интерактору, и после этих запросов вы должны предоставить расположение одной из мин.
В каждом запросе вы выбираете позицию на поле $$$(x, y)$$$, и в качестве ответа вы получите манхэтонское расстояние от выбранной позиции до ближайшей из двух мин, то есть значение $$$\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)$$$.
Ваша задача — определить расположение одной из мин, сделав свои запросы.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^{3}$$$) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^{8}$$$, $$$2 \leq m \leq 10^{8}$$$) — количество строк и столбцов.
Для каждого набора входных данных интеракция начинается с чтения $$$n$$$ и $$$m$$$.
Затем вы можете сделать не более $$$4$$$ запросов следующим образом:
«? x y» ($$$1 \leq x \leq n$$$ и $$$1 \leq y \leq m$$$)
После каждого из них вы должны прочитать число $$$d$$$, которое равняется $$$\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)$$$.
Когда вы нашли расположение любой из мин, выведите в единственной строке «! x y» (без кавычек), обозначающие строку и столбец для этой мины. Вывод ответа не считается за запрос.
После вывода ответа ваша программа должна продолжить решать оставшиеся тестовые случаи или завершиться, если все тестовые случаи были решены.
Интерактор в этой задаче не является адаптивным: расположение мин зафиксировано заранее и не зависит от запросов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы:
Чтобы сделать взлом, используйте следующий формат:
В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^{3}$$$) — количество наборов входных данных.
Описание каждого тестового случая должно состоять из трех строк.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^{8}$$$, $$$2 \leq m \leq 10^{8}$$$) — количество строк и столбцов.
Вторая строка содержит координаты первой мины $$$x_1$$$ и $$$y_1$$$($$$1 \leq x_1 \leq n$$$, $$$1 \leq y_1 \leq m$$$).
Третья строка содержит координаты второй мины $$$x_2$$$ и $$$y_2$$$($$$1 \leq x_2 \leq n$$$, $$$1 \leq y_2 \leq m$$$).
Мины должны располагаться в различных позициях.
2 4 4 3 2 2 0 5 5 1 2 3
? 1 1 ? 1 4 ? 4 1 ? 2 3 ! 2 3 ? 5 5 ? 2 2 ? 3 3 ! 1 1
В первом наборе входных данных мы сначала спрашиваем про верхний левый угол $$$(1, 1)$$$ и получаем результат $$$3$$$, что означает, что есть мина на побочной диагонали, и нет мин над ней.
На картинке ниже каждая клетка содержит число, обозначающее расстояние до синей клетки. Зеленые клетки — кандидаты, в которых содержится ближайшая мина.
Затем мы спрашиваем три клетки на диагонали и в последнем запросе мы получаем результат $$$0$$$, что означает, что одна из мин найдена на позиции $$$(2, 3)$$$.
Вторая мина располагалась на позиции $$$(3, 2)$$$.
Во втором наборе входных данных мы сначала спрашиваем нижний правый угол $$$(5, 5)$$$ и получаем результат $$$1$$$, который означает, что одна из двух соседних клеток содержит мину, назовем ее миной $$$1$$$.
Затем мы спрашиваем клетку $$$(2, 2)$$$. Можем заметить, что зеленые клетки не пересекаются с зелеными клетками из первого запроса, поэтому они содержат оставшуюся мину, назовем ее миной $$$2$$$.
Запрос $$$3$$$ — это клетка $$$(3, 3)$$$. Эти клетки содержат мину $$$1$$$, но мы все еще не знаем, где именно. Тем не менее, мы можем определить, что единственной возможной клеткой для мины $$$2$$$ является клетка $$$(1, 1)$$$, потому что все остальные кандидаты находятся на дистанции менее $$$3$$$ для этого запроса.
