Codeforces Round 523 (Div. 2) |
---|
Закончено |
Граф называется деревом если он связен и не содержит циклов. Предположим, у дерева выбран корень. Тогда дерево называется полным $$$k$$$-ичным если каждая вершина или является листом (не имеет сыновей) или имеет ровно $$$k$$$ сыновей. Также все листья полного $$$k$$$-ичного дерева должны иметь одинаковую глубину.
Например, на картинке ниже изображено полное двоичное дерево из $$$15$$$ вершин.
Выбрано полное $$$k$$$-ичное дерево из $$$n$$$ вершин. Вершины помечены различными целыми числами от $$$1$$$ до $$$n$$$, однако вы не знаете каким именно образом помечены вершины. Тем не менее, вы хотите выяснить пометку у корня дерева.
Вы можете выполнить не более $$$60 \cdot n$$$ запросов следующего вида:
Вершины $$$a$$$ и $$$c$$$ считаются лежащими на пути от $$$a$$$ до $$$c$$$.
Когда вы будете готовы сообщить пометку корня дерева выведите
Разрешается вывести номер корня ровно один раз и эта операция не учитывается относительно ограничения на $$$60 \cdot n$$$ запросов.
Первая строка стандартного потока ввода содержит два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 1500$$$, $$$2 \le k < n$$$) — количество вершин в дереве и значение параметра $$$k$$$.
Гарантируется, что $$$n$$$ таково, что дерево является полным $$$k$$$-ичным.
Вы можете задать не более $$$60 \cdot n$$$ запросов. Чтобы выполнить запрос выведите строку вида «? $$$a$$$ $$$b$$$ $$$c$$$», где $$$1 \le a, b, c \le n$$$. После этого считайте одну строку содержащую или «Yes» или «No», в зависимости от результата запроса.
Дерево зафиксировано для каждого теста и не зависит от запросов вашего решения.
Когда вы готовы вывести ответ, выведите строку вида «! $$$s$$$», где $$$s$$$ является пометкой корня, и завершите вашу программу после этого.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
В случае, если ваша программа сделает более $$$60 \cdot n$$$ запросов, но в остальном будет следовать протоколу взаимодействия и корректно завершится, то вы получите вердикт «Неправильный Ответ».
Взломы
Чтобы взломать решение используйте следующий формат теста:
Первая строка должна содержать целые числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 1500$$$, $$$2 \le k \le 1500$$$) — количество вершин и параметр $$$k$$$ дерева.
Разумеется, значение $$$n$$$ должно соответствовать размеру полного $$$k$$$-ичного дерева какой-то глубины.
Вторая строка должна содержать $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — пометки вершин дерева при их обходе в естественном порядке, все пометки должны быть различными.
Назовём следующий порядок вершин естественным: сначала записан корень дерева, затем записаны все вершины на расстоянии одного ребра в порядке слева направо, затем записаны все вершины на расстоянии двух рёбер в порядке слева направо, и так далее до наибольшей глубины.
В частности, ответом на взлом является $$$a_1$$$.
3 2
No
Yes
? 1 3 2
? 1 2 3
! 2
Дерево в первом примере выглядит следующим образом:
Ввод вывод в примере иллюстрируют возможный сценарий взаимодействия на этом примере (пустые строки добавлены только для наглядности).
Взлом, соответствующий первом тесту выглядел бы так:
3 2
2 3 1
Название |
---|