Bessie et Farmer John visitent Mootreepolis, mais se séparent et elle se perd. Un groupe la cherche ; seul le sens de son meuglement, audible partout en ville, permet de la localiser.
Le transport forme un arbre, comme le nom : $N$ lieux ($1 \le N \le 100,000$), numérotés $0$..$N$-$1$, reliés par $N$-$1$ passages bidirectionnels avec un chemin unique entre deux lieux. Bessie occupe un des $N$ lieux.
Un chercheur se trouve dans chacun des $N$ lieux. FJ peut appeler pour connaître la direction du meuglement, donc le passage vers Bessie, ou savoir qu'elle est là.
Le forfait est cher, il veut minimiser les appels. Indiquez les lieux à appeler, notamment en garantissant au plus $20$ appels avant de donner sa position.
Remarque : dans $50\%$ des entrées $N$ vaut au plus $1000$.
Lisez d'abord la carte sur l'entrée standard, puis interagissez avec le programme de notation par entrée/sortie standard. Chaque ligne initiale liste les passages d'un lieu. Les indices de la liste commencent à zéro, pour l'interaction suivante.
Première ligne $N$, suivantes : voisins des lieux depuis $0$. Premier entier $K$ ($1 \le K \le N$), nombre de voisins, puis $K$ entiers $N_{0}$, $N_{1}$, …, $N_{K-1}$, leurs numéros à partir de zéro. Un passage définit le voisinage.
Affichez successivement les lieux sur la sortie standard. Chaque réponse est l'indice du passage vers Bessie dans la ligne initiale correspondante. Lisez-la sur l'entrée standard.
Afficher son lieu termine automatiquement le programme. Sur QOJ, le programme ferme le flux des réponses lorsqu'elle est trouvée ; terminez normalement à la fin d'entrée en lisant une réponse.
Les réponses peuvent être adaptatives, mais leur ensemble reste compatible avec au moins une position possible.
Si elle est trouvée, score annoncé non nul : au plus $20$ requêtes, actuelle comprise, donne $10$ ; $30$ ou plus donne $0$ ; sinon $30$ moins le nombre de requêtes.
Supposez Bessie au nœud $5$ de la carte ; description d'entrée à droite :
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 table montre une interaction. query est la sortie standard, response l'entrée standard, location le lieu indiqué. details contient la liste complète ordonnée des voisins et l'interprétation en <> :
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
Depuis $2$ et $6$, voisin le plus proche et unique : $3$. Depuis $3$ : $4$, depuis $4$ : $5$. Elle est bien en $5$ ; afficher $5$ termine le programme.
Programmes interactifs
Il faut vider le tampon de sortie pour que les données ne restent pas dans le programme.
C/C++ avec stdio.h : ajoutez :
setbuf(stdout, 0);
près du début du programme.
Pour C++ iostream, videz chaque ligne ainsi :
cout << line << "\n" << flush;
Pascal : après chaque writeln, ajoutez :
flush(stdout);
Java : après chaque instruction de sortie, ajoutez :
System.out.flush();
Un dépassement de temps après une réponse indique probablement une sortie mal vidée.
Utilisateurs de Java
Voici (nous l'espérons) le squelette d'entrée/sortie nécessaire :
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: nœud
Count: nombre
Neighbors: voisins
Query: requête
Response: réponse
Location: lieu
Neighbor list details: détails de la liste des voisins
Done; program will be terminated: terminé, le programme prendra fin
write ...: écrire
read a reply: lire une réponse
Entrée
Ligne $1$ : entier $N$.
Lignes $2..N+1$ : ligne $i+2$, voisins du lieu $i$ par entiers séparés $K$, $N_{0}$, …, $N_{K-1}$.
Sortie
- Aucune ligne dans un fichier de sortie : écrivez sur la sortie standard, pas dans le fichier.
Exemples
Entrée 1
8 1 3 1 4 1 3 4 0 2 6 4 4 3 7 1 5 1 4 1 3 1 4
Sortie 1
Auteur du problème : MIT, 2010