Bessie y Farmer John visitan Mootreepolis, pero se separan y ella se pierde. Organiza un grupo de búsqueda; solo la dirección de su mugido, audible en toda la ciudad, permite localizarla.
El transporte es un árbol, como el nombre: $N$ lugares ($1 \le N \le 100,000$), numerados $0$..$N$-$1$, unidos por $N$-$1$ caminos bidireccionales, ruta única entre cualquier par. Bessie está en uno de $N$ lugares.
Hay un buscador en cada uno de $N$ lugares. FJ puede llamar para oír la dirección del mugido, el camino que lleva hacia ella, o saber que está allí.
El teléfono es caro, quiere minimizar llamadas. Indica dónde llamar, garantizando especialmente no más de $20$ antes de comunicar su posición.
Nota: en $50\%$ de entradas $N$ es como máximo $1000$.
Lee primero el mapa de entrada estándar, luego interactúa con el evaluador por entrada/salida estándar. Cada línea inicial enumera caminos de un lugar, lista indexada desde cero para la interacción.
Primera línea $N$, siguientes: vecinos desde lugar $0$. Primer entero $K$ ($1 \le K \le N$), número de vecinos, luego $K$ enteros $N_{0}$, $N_{1}$, …, $N_{K-1}$, sus índices desde cero. Un camino conecta vecinos.
Imprime lugares sucesivamente. Cada respuesta es el índice del camino hacia Bessie en la línea inicial correspondiente. Lee de entrada estándar.
Imprimir su lugar termina el programa automáticamente. En QOJ el evaluador cierra respuestas al encontrarla; termina normalmente si al leer llegas al final de entrada.
Las respuestas pueden ser adaptativas, pero todas son compatibles con al menos una posición posible.
Al encontrarla se anuncia puntuación no nula: hasta $20$ consultas incluida actual da $10$, $30$ o más da $0$, otras $30$ menos consultas realizadas.
Supón Bessie en nodo $5$ del mapa, descriptor de entrada a la derecha:
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 4La tabla muestra una interacción: query a salida estándar, response desde entrada estándar, location el lugar indicado. details lista completa ordenada de vecinos e interpretación con <>:
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
Desde $2$ y $6$, vecino más cercano y único $3$. Desde $3$, $4$; desde $4$, $5$. Está en $5$, imprimir $5$ termina el programa.
Programas interactivos
Vacía la salida para no dejar datos en el búfer.
C/C++ con stdio.h, incluye:
setbuf(stdout, 0);
cerca del principio del programa.
C++ iostream, vacía cada línea así:
cout << line << "\n" << flush;
Pascal, tras cada writeln, añade:
flush(stdout);
Java, tras cada salida, añade:
System.out.flush();
Un tiempo excedido después de responder probablemente indica que no vacías correctamente.
Usuarios de Java
Aquí (esperamos) está el esqueleto de entrada/salida necesario:
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: nodo
Count: cantidad
Neighbors: vecinos
Query: consulta
Response: respuesta
Location: lugar
Neighbor list details: detalles de vecinos
Done; program will be terminated: listo, el programa terminará
write ...: escribir
read a reply: leer respuesta
Entrada
Línea $1$: entero $N$.
Líneas $2..N+1$: línea $i+2$ describe vecinos del lugar $i$ con enteros separados $K$, $N_{0}$, …, $N_{K-1}$.
Salida
- Ninguna línea de archivo de salida: escribe a salida estándar, no al archivo.
Ejemplos
Entrada 1
8 1 3 1 4 1 3 4 0 2 6 4 4 3 7 1 5 1 4 1 3 1 4
Salida 1
Autor del problema: MIT, 2010