| Codeforces Round 1118 (Div. 2) |
|---|
| Закончено |
Это интерактивная задача.
Сефероглу живёт в небольшом прибрежном городе Самсун, где не так много людей занимается спортивным программированием. Каждый раз, когда проходит какое-либо мероприятие, ему приходится ездить в далёкие города, чтобы встретиться с друзьями. Поскольку ему надоело каждый раз точно вычислять длину своего пути, он хочет лишь узнать максимальное расстояние, которое ему когда-либо придётся преодолеть между двумя городами в худшем случае. Ваша задача — помочь ему найти это расстояние, сделав как можно меньше запросов.
Задано скрытое дерево$$$^{\text{∗}}$$$ с $$$n$$$ вершинами. Вы можете делать запросы. В одном запросе вы выбираете две вершины $$$1 \le u, v \le n$$$ и целое число $$$0 \le d \le n$$$; жюри отвечает $$$1$$$, если $$$\operatorname{dist}(u, v) \ge d$$$, и $$$0$$$ в противном случае. Через $$$\operatorname{dist}(u,v)$$$ обозначается расстояние$$$^{\text{†}}$$$ между вершинами $$$u$$$ и $$$v$$$ в дереве.
Ваша задача — определить длину диаметра$$$^{\text{‡}}$$$ и найти любую пару вершин, расстояние между которыми равно диаметру. Вы можете задать не более $$$3 \cdot n$$$ запросов.
$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.
$$$^{\text{†}}$$$Расстоянием между двумя вершинами в дереве называется количество рёбер в единственном простом пути между этими вершинами.
$$$^{\text{‡}}$$$Длина диаметра это наибольшее расстояние среди всех пар вершин.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержится $$$n$$$ ($$$2 \le n \le 1000$$$) — количество вершин в дереве.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Чтобы сделать запрос, сначала выберите $$$u$$$, $$$v$$$ и $$$d$$$ ($$$1 \le u, v \le n$$$, $$$0 \le d \le n$$$) — пару вершин и величину, с которой нужно сравнить расстояние между ними, — а затем выведите следующую строку (без кавычек):
- "? u v d"
После этого считайте одно целое число ($$$1$$$ или $$$0$$$), показывающее, было ли $$$d$$$ меньше либо равно $$$\text{dist}(u, v)$$$.
Заметим, что можно задать не более $$$3 \cdot n$$$ таких запросов.
Затем, если ваша программа нашла ответ, она должна вывести следующую строку (без кавычек):
- "! u v d"
Здесь выбранные $$$u$$$ и $$$v$$$ обозначают концы диаметра ($$$1 \le u, v \le n$$$), а указанное после них число — длину пути между ними ($$$0 \le d \le n-1$$$). Если существует несколько ответов, можно вывести любой из них.
Заметим, что это действие не учитывается в ограничении на максимальное количество запросов.
Жюри не адаптивно. Это означает, что граф фиксируется в начале и не изменяется в зависимости от ваших запросов.
После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».
На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.
Взломы
Для взломов используйте следующий формат:
В первой строке содержится количество наборов входных данных $$$t$$$ ($$$1 \le t \le 500$$$).
В первой строке каждого набора входных данных содержится $$$n$$$ ($$$2 \le n \le 1000$$$) — количество вершин в дереве.
В следующих $$$n-1$$$ строках каждого набора входных данных содержатся по два целых числа $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — рёбра дерева.
$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:
- fflush(stdout) или cout.flush() в C++;
- sys.stdout.flush() в Python;
- смотрите документацию для других языков.
3 4 1 0 0 0 2 4 1 1 1 1 0 0 0 0
? 1 2 1 ? 1 2 2 ? 2 3 2 ? 3 4 2 ! 1 4 3 ! 1 2 1 ? 1 2 1 ? 1 3 1 ? 1 4 1 ? 3 4 2 ? 3 4 3 ? 1 2 2 ? 1 3 2 ? 1 4 2 ! 4 2 2
Скрытый граф в первом наборе входных данных имеет рёбра $$$(1,2), (2,3), (3,4)$$$.
Скрытый граф во втором наборе входных данных имеет ребро $$$(1,2)$$$.
Скрытый граф в третьем наборе входных данных имеет рёбра $$$(1,2), (1,3), (1,4)$$$.
В третьем наборе входных данных ответ "! 3 4 2" также является корректным.
 |  |  | |
| Дерево из первого набора входных данных | Дерево из второго набора входных данных | Дерево из третьего набора входных данных |
