Dies ist eine interaktive Aufgabe.

Hintergrund

Nach einem halben Jahr kann I 君 seinen Laden schließlich nicht mehr weiterführen. Er beschließt, ihn abzugeben und als Abenteurer die weite unbekannte Welt zu erkunden.

Nach den Aufzeichnungen eines alten Buchs findet er im Herzen einer großen Wüste einen unterirdischen Palast einer unbekannten Zivilisation. Er besteht aus $N$ großen Höhlen und $M$ Durchgängen, die sie in beide Richtungen verbinden. Mithilfe des Buchs kann I 君 erkennen, in welcher Höhle er sich befindet. Das Buch verzeichnet jedoch nicht, wie die $M$ Durchgänge die Höhlen verbinden. Daher kann er nur schwer nach den unermesslichen Schätzen suchen, die der Legende nach im Palast verborgen sind.

Nun hat I 君 jedoch einen geheimnisvollen Mechanismus entdeckt, der Informationen über den Palast liefert. Er möchte damit dessen Verbindungsstruktur ermitteln und bittet dich um Hilfe.

Aufgabenstellung

Der unterirdische Palast lässt sich als einfacher ungerichteter Graph mit $N$ Knoten und $M$ Kanten darstellen. In einem einfachen Graphen gibt es zwischen je zwei Knoten höchstens eine direkte Kante. Die Höhlen sind von $0$ bis $n-1$ nummeriert. Du weißt derzeit nicht, welche Kanten existieren.

Jede Höhle besitzt eine Lichtquelle, die ein- oder ausgeschaltet sein kann. Nur eine eingeschaltete Lichtquelle beleuchtet ihre Höhle. Anfangs sind alle Lichtquellen ausgeschaltet. Ihre Zustände lassen sich ausschließlich mit dem von I 君 entdeckten Mechanismus ändern. Genauer gesagt erlaubt er vier Operationen:

1. Gib dem Mechanismus eine Nummer $x$. Er schaltet die Lichtquellen der Höhle $x$ und aller direkt mit ihr durch einen Durchgang verbundenen Höhlen um: Eingeschaltete werden aus-, ausgeschaltete eingeschaltet.
2. Gib ihm eine Nummer $x$. Er zeigt den aktuellen Zustand der Lichtquelle in Höhle $x$ an.
3. Gib ihm zwei Nummern $x,y$. Damit erklärst du, dass du sicher bist, dass ein Durchgang zwischen den Höhlen $x,y$ existiert, und lässt ihn diesen verzeichnen.
4. Gib ihm eine Nummer $x$. Er prüft, ob alle mit Höhle $x$ verbundenen Durchgänge bereits verzeichnet sind.

Die nächste Operation kann erst nach Abschluss der vorherigen ausgeführt werden. Der Mechanismus darf nicht beliebig oft verwendet werden: Die Anzahlen der vier Operationen sind der Reihe nach auf $L_m,L_q,M,L_c$ beschränkt. Schreibe ein Programm, das I 君 hilft, den Mechanismus sinnvoll einzusetzen und alle $M$ Durchgänge richtig zu finden.

Implementierungsdetails

Du musst und sollst keine Hauptfunktion implementieren. Implementiere nur explore(N, M), wobei N und M die Anzahlen der Höhlen und Durchgänge sind. Über die folgenden vier Funktionen kannst du mit der Interaktionsbibliothek kommunizieren:

modify(x)

• Führt Operation 1 mit der Nummer $x$ aus.
• Du musst $0\le x<N$ gewährleisten. Die Funktion hat keinen Rückgabewert.

query(x)

• Führt Operation 2 mit der Nummer $x$ aus.
• Du musst $0\le x<N$ gewährleisten. Die Funktion gibt 0 oder 1 zurück: 0 bedeutet, dass die Lichtquelle der Höhle $x$ derzeit ausgeschaltet ist, 1, dass sie eingeschaltet ist.

report(x, y)

• Führt Operation 3 mit den Nummern $x,y$ aus.
• Du musst $0\le x,y<N$ und $x\ne y$ gewährleisten. Die Funktion hat keinen Rückgabewert.

check(x)

• Führt Operation 4 mit der Nummer $x$ aus.
• Du musst $0\le x<N$ gewährleisten. Die Funktion gibt 0 oder 1 zurück, wobei sie genau dann 1 zurückgibt, wenn alle mit Höhle $x$ verbundenen Durchgänge bereits durch Operation 3 verzeichnet wurden.

Bei der Bewertung ruft die Interaktionsbibliothek explore genau einmal auf.

Es ist garantiert, dass der verwendete Graph bereits vor Beginn der Interaktion vollständig feststeht und während der Interaktion mit deinem Programm nicht dynamisch konstruiert wird. Alle Interaktionsoperationen dieser Aufgabe sind daher deterministisch. Du musst dich nicht darum kümmern, wie die Bibliothek diese Operationen im Einzelnen implementiert.

Die Daten garantieren, dass die Interaktionsbibliothek bei Einhaltung der Aufrufgrenzen höchstens 1 Sekunde Laufzeit benötigt. Ihr Speicherbedarf ist fest und beträgt höchstens 128 MB.

Implementierung

Im Arbeitsverzeichnis liegt bereits eine Datei template_explore.cpp/c/pas. Kopiere sie, benenne die Kopie in explore.cpp/c/pas um und bearbeite die Aufgabe auf dieser Grundlage.

Für C++-/C-Teilnehmer

Stelle sicher, dass dein Programm am Anfang #include "explore.h" enthält.

Die Schnittstelle der von dir zu implementierenden Funktion explore lautet:

void explore(int N, int M);

Die Schnittstellen der aufrufbaren Interaktionsfunktionen lauten:

void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);

Für Pascal-Teilnehmer

Die Syntax zur Implementierung der Schnittstelle ist in Pascal recht kompliziert. Bearbeite daher direkt die bereitgestellte Datei template_explore.pas, statt den Code selbst von Grund auf zu schreiben.

Die Schnittstelle der zu implementierenden Funktion explore lautet:

procedure _explore(N, M : longint);

Beachte, dass der Funktionsname hier _explore und nicht explore lautet. Der Name explore führt zu einem Kompilierungsfehler.

Die Schnittstellen der aufrufbaren Interaktionsfunktionen lauten:

procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;

Dein Programm testen

Die Dateien grader.cpp/c und graderhelperlib.pas im Aufgabenverzeichnis sind unsere Referenzimplementierung der Interaktionsbibliothek. Die bei der endgültigen Bewertung verwendete Implementierung unterscheidet sich davon. Deine Lösung darf deshalb nicht von der konkreten Bibliotheksimplementierung abhängen.

Für C-/C++-Teilnehmer

Kompiliere im Aufgabenverzeichnis mit den folgenden Befehlen eine ausführbare Datei.

Für C:

gcc grader.c explore.c -o explore -O2 -lm

Für C++:

g++ grader.cpp explore.cpp -o explore -O2 -lm

Für Pascal-Teilnehmer

Kompiliere im Aufgabenverzeichnis mit folgendem Befehl eine ausführbare Datei:

fpc grader.pas -o"explore" -O2

Für die erzeugte ausführbare Datei

Sie liest Daten im folgenden Format von der Standardeingabe:

Die erste Zeile enthält drei ganze Zahlen $L_m,L_q,L_c$, die zweite zwei ganze Zahlen $N,M$ mit der in der Aufgabenstellung beschriebenen Bedeutung.

Es folgen $M$ Zeilen mit jeweils zwei ganzen Zahlen $x,y$, die einen Durchgang zwischen den Höhlen $x,y$ beschreiben.

Nach dem Einlesen ruft die Bibliothek die Funktion explore genau einmal auf und testet sie mit den eingelesenen Daten. Nachdem deine Funktion korrekt zurückgekehrt ist, prüft die Bibliothek deine Berechnung. Ist sie richtig, gibt sie Correct und Informationen über die Anzahlen der Interaktionsaufrufe aus, andernfalls eine entsprechende Fehlermeldung.

Interaktion

Angenommen, die ausführbare Datei liest folgende Daten:

100 200 300
3 2
0 1
1 2

Die drei Zahlen der ersten Zeile sind die Aufrufgrenzen der drei Operationen: modify(x) darf höchstens $100$ Mal, query(x) höchstens $200$ Mal und check(x) höchstens $300$ Mal aufgerufen werden.

Die beiden Zahlen der zweiten Zeile geben die Anzahlen der Höhlen und Durchgänge an, also $N=3$, $M=2$.

report(x, y) darf höchstens $M$ Mal aufgerufen werden, in diesem Beispiel also höchstens $2$ Mal.

Eine korrekte Interaktion ist wie folgt:

Bereitgestellte Dateien

Im Aufgabenverzeichnis liegen:

1. grader.cpp/c und graderhelperlib.pas, unsere Referenzimplementierung der Interaktionsbibliothek.
2. explore.h und grader.pas, Headerdateien, deren genauen Inhalt du nicht kennen musst.
3. template_explore.cpp/c/pas, unser Beispielquellcode für eine Lösung.
4. explore1.in, explore2.in, explore3.in, Beispieleingaben zum Testen.

Sichere alle bereitgestellten Dateien. Bei der Bewertung wird nur explore.c/cpp/pas aus diesem Aufgabenverzeichnis eingesammelt. Änderungen an anderen Dateien sind wirkungslos.

Teilaufgaben

Bei der endgültigen Bewertung wird nur explore.cpp/c/pas eingesammelt. Änderungen an anderen Dateien im Teilnehmerverzeichnis sind wirkungslos.

Zunächst gelten dieselben Einschränkungen wie für gewöhnliche Aufgaben. Beispielsweise führt ein Kompilierungsfehler zu 0 Punkten für die gesamte Aufgabe. Laufzeitfehler sowie Überschreitungen von Zeit- oder Speichergrenzen führen zu 0 Punkten im jeweiligen Testfall. Du darfst nur auf selbst definierte und von der Interaktionsbibliothek bereitgestellte Variablen und die zugehörigen Speicherbereiche zugreifen. Zugriffe auf andere Bereiche können Kompilierungs- oder Laufzeitfehler verursachen.

Unter diesen Voraussetzungen erhältst du für einen Testfall genau dann die volle Punktzahl, wenn:

1. Jeder deiner Funktionsaufrufe gültig ist und die Anzahlen der Aufrufe von modify, query, check höchstens $L_m,L_q,L_c$ betragen.
2. Da report höchstens $M$ Mal aufgerufen werden darf, jeder Aufruf eine neue, tatsächlich vorhandene Kante verzeichnet. Bei jedem Aufruf report(x, y) muss also ein Durchgang zwischen den Höhlen $x,y$ existieren, und zuvor darf weder report(x, y) noch report(y, x) aufgerufen worden sein.
3. Deine Funktion explore normal zurückkehrt.
4. Beim Zurückkehren von explore alle $M$ Durchgänge durch report verzeichnet sind.

Beschränkungen

Es gibt 25 Testfälle mit jeweils 4 Punkten. Ihre Größen und Einschränkungen stehen in der folgenden Tabelle:

Noch einmal: Der für die Tests verwendete Graph steht garantiert vor Beginn der Interaktion vollständig fest und wird nicht während der Interaktion mit deinem Programm dynamisch konstruiert.

Die besonderen Eigenschaften in der Tabelle bedeuten:

A: Jeder Knoten hat garantiert genau den Grad $1$.

B: Für jedes $x>0$ existiert genau ein $y<x$, sodass die Höhlen $x,y$ direkt durch einen Durchgang verbunden sind.

C: Es gibt eine Permutation $p_0,p_1,\ldots,p_{N-1}$ von $0$ bis $N-1$, sodass für jedes $1\le i<N$ ein Durchgang zwischen den Höhlen $p_{i-1},p_i$ existiert.

D: Der Graph ist garantiert zusammenhängend.

• Hinweis: Dein Programm kann die verschiedenen Datentypen anhand der Einerstelle des übergebenen Werts $N$ unterscheiden.