Codeforces Round 559 (Div. 1) |
---|
Закончено |
Это интерактивная задача.
Вася обожает решать загадки и разгадывать головоломки. На этот раз он нашел странный прибор и хочет выяснить принцип его работы.
Этот прибор зашифрован с помощью дерева (связного неориентированного графа без циклов), состоящего из $$$n$$$ вершин, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Чтобы решить головоломку надо угадать это дерево.
К счастью прибор умеет выполнять одну операцию, исходя из которой надо разгадать его шифр. Можно ввести в прибор последовательность $$$d_1, d_2, \ldots, d_n$$$ целых неотрицательных чисел. На приборе есть $$$n$$$ лампочек, $$$i$$$-я из которых отвечает за $$$i$$$-ю вершину дерева-шифра. Для всех $$$i$$$ из этих лампочек $$$i$$$-я загорится, если существует такая вершина дерева-шифра с номером $$$j \neq i$$$, что $$$dist(i, j) \leq d_j$$$. Здесь $$$dist(i, j)$$$ обозначает расстояние между вершинами $$$i$$$ и $$$j$$$ в дереве-шифре, то есть количество ребер в простом пути между вершинами $$$i$$$ и $$$j$$$.
Вася хочет за $$$\leq 80$$$ операций с прибором решить головоломку и угадать дерево-шифр. Помогите ему!
В начале вашей программе вводится единственное целое число $$$n$$$ — количество вершин в дереве-шифре прибора ($$$2 \leq n \leq 1000$$$).
Далее вы можете выполнять операции в следующем формате. Сначала выведите символ "?" (без кавычек) и за ним $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$, разделенных пробелами. Заметьте, что в операциях для всех $$$i$$$ должно быть выполнено неравенство $$$0 \leq d_i < n$$$. В ответ будет выведена строка $$$s$$$ длины $$$n$$$, состоящая из символов "0" и "1" (без кавычек). Для всех $$$i$$$ символ $$$s_i$$$ будет равен "0", если у прибора не включилась лампочка, соответствующая $$$i$$$-й вершине дерева-шифра и "1", иначе.
После нескольких запросов вы должны вывести угаданное дерево. Для этого в первой строке выведите единственный символ "!" (без кавычек). В следующих $$$n-1$$$ строках выведите по $$$2$$$ целых числа $$$a_i$$$, $$$b_i$$$ — номера вершин, соединяющих $$$i$$$-е ребро дерева. Выведенные числа должны удовлетворять условиям $$$1 \leq a_i, b_i \leq n$$$ и $$$a_i \neq b_i$$$. Эти ребра должны образовывать дерево, совпадающее с загаданным. Выводить ребра можно в любом порядке. После этого ваша программа должна завершиться.
Гарантируется, что в каждом тесте дерево-шифр будет зафиксировано заранее и не будет меняться в зависимости от выполняемых операций.
Ваша программа может выполнить от $$$0$$$ до $$$80$$$ операций с прибором и после этого сообщить дерево, совпадающее с загаданным.
Если ваша программа сделает больше $$$80$$$ операций, то она может получить любой вердикт, потому что будет считывать данные из закрытого потока ввода. Также, если ваша программа сделает операцию или выведет ответ в неверном формате, она может получить любой вердикт. Будьте внимательны.
Не забудьте сбрасывать буфер вывода после того, как выведете данные для операции или ответ.
Чтобы сбросить буфер вывода вы можете использовать:
Взломы:
Первая строка должна содержать единственное целое число $$$n$$$ — количество вершин в дереве-шифре ($$$2 \leq n \leq 1000$$$). Следующая $$$n-1$$$ строка должна содержать по $$$2$$$ целых числа $$$a_i$$$, $$$b_i$$$ — номера вершин, соединяющих $$$i$$$-е ребро дерева ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$). Выведенные ребра должны образовывать дерево. Будьте внимательны, лишние пробелы или переводы строк запрещены.
5 00000 11011 11100 10010
? 0 0 0 0 0 ? 1 1 2 0 2 ? 0 0 0 1 0 ? 0 1 0 0 1 ! 4 2 1 5 3 4 4 1
Дерево-шифр из первого теста выглядит так:
Таблица попарных расстояний между вершинами выглядит так:
Название |
---|