Bessie und Farmer John besuchen Mootreepolis, werden getrennt, sie verirrt sich. Ein Suchtrupp sucht sie; einziger Hinweis ist die Richtung ihres stadtweit hörbaren Muhens.

Verkehr ist wie der Name ein Baum: $N$ Orte ($1 \le N \le 100,000$), nummeriert $0$..$N$-$1$, durch $N$-$1$ Wege in beide Richtungen verbunden, genau ein Weg zwischen jedem Paar. Bessie in einem der $N$ Orte.

An jedem der $N$ Orte steht ein Sucher. FJ kann anrufen, erfährt Muh-Richtung, also welcher Weg zu Bessie führt, oder dass sie dort ist.

Telefon teuer, er möchte minimale Anrufzahl. Wähle Orte zum Anrufen, insbesondere höchstens $20$ bis zur Ortsmeldung.

Hinweis: in $50\%$ der Eingaben ist $N$ höchstens $1000$.

Lies zuerst Karte von Standardeingabe, interagiere dann mit Prüfer über Standardein-/ausgabe. Anfangszeilen listen Wege je Ort, Liste mit Index ab null, später relevant.

Erste Zeile $N$, folgende: Nachbarn beginnend bei Ort $0$. Erstes $K$ ($1 \le K \le N$), Nachbarzahl, dann $K$ ganze Zahlen $N_{0}$, $N_{1}$, …, $N_{K-1}$, Nachbarindizes ab null. Ein Weg macht Orte benachbart.

Gib nacheinander Orte aus. Antwort ist Index des Weges zu Bessie innerhalb der entsprechenden Eingabezeile. Lies von Standardeingabe.

Ihr Ort als Ausgabe beendet automatisch. Auf QOJ schließt der Prüfer den Antwortstrom beim Fund; beende normal bei Eingabeende beim Antwortlesen.

Antworten dürfen adaptiv sein, bleiben aber alle mit wenigstens einer möglichen Position vereinbar.

Beim Fund wird eine Punktzahl ungleich null angekündigt: bis $20$ Anfragen einschließlich aktueller gibt $10$, ab $30$ gibt $0$, sonst $30$ minus Anfragezahl.

Sei Bessie an Knoten $5$ der Karte, Eingabebeschreibung rechts:

                               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

Interaktionstabelle: query eigene Standardausgabe; response eigene Standardeingabe; location angegebener Ort. details vollständige geordnete Nachbarliste mit Deutung durch <>:

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

Von $2$, $6$ nächster und einziger Nachbar $3$. Von $3$ ist es $4$, von $4$ ist es $5$. Sie ist an $5$, Ausgabe $5$ beendet das Programm.

Interaktive Programme

Leere den Ausgabepuffer, damit nichts im Programm bleibt.

C/C++ mit stdio.h, füge ein:

setbuf(stdout, 0);

nahe dem Programmanfang.

C++ iostream, leere jede Ausgabezeile so:

cout << line << "\n" << flush;

Pascal nach jedem writeln:

flush(stdout);

Java nach jeder Ausgabe:

System.out.flush();

Zeitüberschreitung nach Antwort bedeutet vermutlich fehlendes korrektes Leeren.

Java-Benutzer

Hier (hoffentlich) das Gerüst nötiger Ein-/ausgabe:

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: Knoten

Count: Anzahl

Neighbors: Nachbarn

Query: Anfrage

Response: Antwort

Location: Ort

Neighbor list details: Nachbarlistendetails

Done; program will be terminated: fertig, Programm wird beendet

write ...: schreiben

read a reply: Antwort lesen

Eingabe

• Zeile $1$: ganze Zahl $N$.

• Zeilen $2..N+1$: Zeile $i+2$ beschreibt Nachbarn von Ort $i$ mit getrennten ganzen Zahlen $K$, $N_{0}$, …, $N_{K-1}$.

Ausgabe

• Keine Zeile in Ausgabedatei: schreibe auf Standardausgabe, nicht in Datei.

Beispiele

Eingabe 1

8
1 3
1 4
1 3
4 0 2 6 4
4 3 7 1 5
1 4
1 3
1 4

Ausgabe 1

Aufgabenautor: MIT, 2010