Bessie и Farmer John приехали в Mootreepolis, но разделились, и она потерялась. Создан поисковый отряд; единственный способ поиска — направление её мычания, слышимого во всём городе.
Транспорт, как в названии, — дерево: $N$ мест ($1 \le N \le 100,000$), номера $0$..$N$-$1$, $N$-$1$ двусторонних дорожек, единственный путь между любыми двумя. Bessie в одном из $N$ мест.
В каждом из $N$ мест стоит участник поиска. FJ может позвонить и узнать направление звука — какую дорожку выбрать к Bessie, или что её нашли прямо там.
Связь дорогая, нужно минимум звонков. Укажите места для звонков, особенно гарантируя не более $20$ до определения позиции.
Примечание: в $50\%$ входов $N$ не более $1000$.
Сначала прочитайте карту из стандартного ввода, затем взаимодействуйте с проверяющей программой через стандартный ввод/вывод. Начальные строки перечисляют дорожки каждого места; индексы списка начинаются с нуля и нужны далее.
Первая строка $N$, далее соседи мест начиная с $0$. Первый $K$ ($1 \le K \le N$) — число соседей, затем $K$ целых $N_{0}$, $N_{1}$, …, $N_{K-1}$ — их номера с нуля. Дорожка означает соседство.
Выводите последовательность мест. На каждый вывод проверяющая программа отвечает индексом дорожки к Bessie в списке соответствующей начальной строки. Читайте ответ из стандартного ввода.
При выводе позиции Bessie программа завершается автоматически. На QOJ проверяющая программа закрывает поток ответов; нормально завершитесь при конце ввода во время чтения ответа.
Ответы могут выбираться адаптивно, но все согласованы хотя бы с одной возможной позицией.
При нахождении объявлены ненулевые баллы; конкретно: не более $20$ запросов, включая текущий, — $10$; $30$ и более — $0$; иначе $30$ минус число запросов.
Пусть Bessie в узле $5$ карты ниже; описание ввода справа:
Node Count Neighbors
0 1 0 1 3
| | 1 1 4
2--3---4--5(B) 2 1 3
| | 3 4 0 2 6 4
6 7 4 4 3 7 1 5
5 1 4
6 1 3
7 1 4Таблица показывает взаимодействие: query — стандартный вывод, response — стандартный ввод, location — место по ответу. details — полный упорядоченный список соседей запроса с интерпретацией в <>:
Query Response Location Neighbor list details 2 0 3 <3> 6 0 3 <3> 3 3 4 0 2 6 <4> 4 3 5 3 7 1 <5> 5 Done; program will be terminated
Из $2$ и $6$ ближайший и единственный сосед — $3$. Из $3$ — $4$, из $4$ — $5$. Она действительно в $5$, после вывода $5$ программа завершается.
Интерактивные программы
Сбрасывайте выходной буфер, чтобы вывод не оставался внутри программы.
C/C++ с stdio.h: добавьте:
setbuf(stdout, 0);
рядом с началом программы.
Для C++ iostream сбрасывайте каждую строку так:
cout << line << "\n" << flush;
Pascal: после каждого writeln добавьте:
flush(stdout);
Java: после каждого вывода добавьте:
System.out.flush();
Тайм-аут после ответа часто означает отсутствие правильного сброса.
Пользователи Java
Ниже (надеемся) каркас необходимых операторов ввода/вывода:
import java.io.*; import java.util.*;
public class cowtree {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));
/* write ... */
System.out.println(...);
System.out.flush(); /* read a reply */
response = in.readLine();
...Node: узел
Count: количество
Neighbors: соседи
Query: запрос
Response: ответ
Location: место
Neighbor list details: подробности списка соседей
Done; program will be terminated: готово, программа завершится
write ...: запись
read a reply: чтение ответа
Входные данные
Строка $1$: целое $N$.
Строки $2..N+1$: строка $i+2$ описывает соседей места $i$ целыми через пробел $K$, $N_{0}$, …, $N_{K-1}$.
Выходные данные
- Строк в выходном файле нет: пишите в стандартный вывод, не в файл.
Примеры
Входные данные 1
8 1 3 1 4 1 3 4 0 2 6 4 4 3 7 1 5 1 4 1 3 1 4
Выходные данные 1
Автор задачи: MIT, 2010