Codeforces Global Round 22 |
---|
Закончено |
Это интерактивная задача.
Дан простой неориентированный граф с $$$n$$$ вершинами пронумерованными от $$$1$$$ до $$$n$$$, ваша задача состоит в том, чтобы покрасить все вершины так, чтобы для каждого цвета $$$c$$$, выполнялись следующие условия:
Исходно вам дано только $$$n$$$ - число вершин и степень каждой вершины.
Каждым запросом вы можете выбрать вершину $$$u$$$. В ответ вы получите $$$k$$$-е ребро, исходящее из $$$u$$$, если это $$$k$$$-й запрос к вершине $$$u$$$.
Вы можете сделать максимум $$$n$$$ запросов.
Неориентированный граф называется простым, если он не содержит кратных ребер и петель.
Степень вершины это число ребер, исходящих из нее.
Множество вершин $$$S$$$ называется связным если для любых двух различных вершин $$$u, v \in S$$$, существует путь, который проходит только по вершинам множества $$$S$$$, и соединяет $$$u$$$ и $$$v$$$. Формально, существует последовательность ребер $$$(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)$$$ с $$$k \geq 1$$$ такая, что
Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Следующие строки содержат описание и интерактивную часть каждого набора входных данных.
Для каждого набора входных данных вы начинаете взаимодействие с итерактором с чтения целого числа $$$n$$$ ($$$1\le n \le 1000$$$) в первой строке, означающего число вершин в графе.
Вторая строка содержит $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$0 \leq d_i \leq n - 1$$$), где $$$d_i$$$ это степень вершины $$$i$$$.
Чтобы совершить запрос к вершине $$$u$$$ ($$$1 \leq u \leq n$$$), вы должны вывести
Чтобы дать ответ вы должны вывести
Гарантируется, что дан простой неориентированный граф.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
В случае, если формат запроса неверный, или вы сделали более $$$n$$$ «?» запросов, вы получите вердикт Неправильный Ответ.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Формат взломов
Первая строка взлома должна содержать целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$), означающее число наборов входных данных. Следующие строки содержат описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$), означающее число вершин в графе.
Затем следуют $$$n$$$ строк. В $$$i$$$-й строке содержится целое число $$$d_i$$$ ($$$0 \leq d_i \leq n - 1$$$), означающее степень вершины $$$i$$$, и затем $$$d_i$$$ различных целых чисел $$$e_{i,1}, e_{i,2}, \dots, e_{i,d_i}$$$ ($$$1 \leq e_{i, j} \leq n$$$ и $$$e_{i,j} \neq i$$$), где $$$\left(i, e_{i,j}\right)$$$ это $$$j$$$-е ребро, исходящее из вершины $$$i$$$.
Вы должны гарантировать, что граф является простым и неориентированным.
Вы должны гарантировать, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
1 5 2 2 2 2 0 2 4 2 4
? 1 ? 1 ? 3 ? 3 ! 1 1 2 2 3
В примере только один набор входных данных.
В нем $$$n = 5$$$ вершин, из которых $$$1, 2, 3, 4$$$ имеют степень $$$2$$$ и вершина $$$5$$$ имеет степень $$$0$$$. Это означает, что вершина $$$5$$$ изолированная - не соединена ни с одной другой вершиной.
Возможное взаимодействие с итерактором показано во вводе и выводе примера, использовано $$$4$$$ «?» запроса. Из них два к вершине $$$1$$$ и два к вершине $$$3$$$. Исходя из результатов этих запросов мы знаем, что вершины $$$1$$$ и $$$3$$$ соединены с вершинами $$$2$$$ и $$$4$$$.
Возможное решение показано, вершины $$$1$$$ и $$$2$$$ покрашены в цвет $$$1$$$, вершины $$$3$$$ и $$$4$$$ покрашены в цвет $$$2$$$, и вершина $$$5$$$ покрашена в цвет $$$3$$$. Легко заметить, что решение удовлетворяет условиям.
Название |
---|