Räuber und Gendarm

 2014-1c-copsandrobbers.jpg?400

Maus Stofl wurde von Scotland Yard angefragt, bei der Suche und der Verhaftung der gefährlichen Maus X zu helfen. Deine Aufgabe ist es, die Polizisten durch die Strassen von London zu dirigieren, sodass es für Maus X keinen Fluchtweg mehr gibt. Oder bist du abenteuerlustig? Du kannst Maus X auch dabei unterstützen, den Polizisten so lange wie möglich zu entgehen.

Das Spiel

Die Stadt ist als ein Graph modelliert, der aus $N$ Kreuzungen und $M$ Strassen besteht, wobei jede Strasse zwei verschiedene Kreuzungen verbindet. Zwischen jedem gegebenen Paar von Kreuzungen gibt es höchstens eine Strasse und jede Strasse kann in beide Richtungen benutzt werden. Der Graph ist zusammenhängend, das heisst, dass es für jedes Paar von Kreuzungen möglich ist durch Benutzen einer Folge von Strassen von der einen zur anderen zu gelangen.

Es gibt $C+1$ Mäuse. Eine davon ist Maus X. Sie wird vom ersten Programm gesteuert. Die restlichen $C$ sind Polizisten. Sie werden vom zweiten Programm gesteuert.

Zu Beginn des Spiels sind die Mäuse zufällig auf den Kreuzungen verteilt. Es wird garantiert, dass keine zwei Mäuse auf derselben Kreuzung beginnen, und dass keine zwei Mäuse auf benachbarten Kreuzungen beginnen (d.h. zwei Kreuzungen, die durch eine Strasse verbunden sind.)

Das Spiel wird in Runden gespielt. In jeder Runde bewegt sich Maus X zuerst und danach bewegen sich alle Polizisten gleichzeitig.

Die folgenen Züge sind erlaubt:

  • Bewegung auf eine benachbarte Kreuzung.
  • Auf derselben Kreuzung bleiben.

Merke, dass es erlaubt ist, mehrere Polizisten gleichzeitig auf derselben Kreuzung stehen zu haben.

Das Spiel endet sobald eines der folgenden Dinge passiert:

  • Maus X bewegt sich auf eine Kreuzung, die von einem oder mehreren Polizisten besetzt ist. In diesem Fall gewinnen die Polizisten.
  • Ein Polizist bewegt sich auf die Kreuzung, wo Maus X steht. In diesem Fall gewinnen die Polizisten.
  • $R$ Runden sind gespielt, ohne dass Maus X gefangen wurde. In diesem Fall gewinnt Maus X.

Eingabe und Ausgabe

Dein Programm wird von einem Spiel-Server gestartet. Es muss von stdin lesen und muss seine Züge nach stdout ausgeben.

Wenn das Spiel beginnt, wird dir eine Zeile gegeben, die den Buchstaben «P» enthält, falls du die Polizisten spielen sollst, oder «X», falls du Maus X spielen sollst.

Danach bekommst du eine Zeile mit der ganzen Zahl $C$, gefolgt durch eine Zeile mit der ganzen Zahl $R$.

Schliesslich wird dir der Graph gegeben, welcher das Strassensystem der Stadt beschreibt, und zwar im folgenden Format: Eine Zeile mit zwei ganzen Zahlen $N$ und $M$, geteilt durch ein einzelnes Leerzeichen, gefolgt von $M$ Zeilen, wovon jede Zeile zwei ganze Zahlen $a_i$ und $b_i$ enthält, die anzeigen, dass es zwischen den Kreuzungen $a_i$ und $b_i$ eine Strasse gibt. Kreuzungen sind von $1$ bis $N$ durchnummeriert und $1 \leq a_i, b_i \leq N$.

Dann liest du die Anfangsposition(en) deiner Spieler: Falls du Maus X spielst, ist dies eine Zeile mit einer einzelnen Kreuzungsnummer und falls du die Polizisten spielst, ist dies eine Zeile mit $C$ Leerzeichen-getrennten Kreuzungsnummern, wobei die $i$-te Nummer die Kreuzung beschreibt, wo der $i$-te Polizist das Spiel beginnt. Die Reihenfolge der Polizisten in der Eingabe bleibt während des ganzen Spiels dieselbe.

Danach wird Runde um Runde gespielt.

Falls du Maus X spielst, läuft eine Runde wie folgt ab:

  • Du bekommst eine Zeile mit $C$ Leerzeichen-getrennten ganzen Zahlen, die beschreiben, auf welchen Kreuzungen die Polizisten sich momentan befinden.
  • Du musst eine ganze Zahl ausgeben, die Nummer der Kreuzung, auf welche du dich bewegen möchtest.

Falls du die Polizisten spielst, läuft eine Runde wie folgt ab:

  • Du bekommst eine Zeile mit einer einzelnen ganzen Zahl, die die Kreuzung beschreibt, auf der sich Maus X gerade befindet.
  • Du musst $C$ Leerzeichen-getrennte ganze Zahlen ausgeben, wobei die $i$-te Zahl die Nummer der Kreuzung ist, auf welche du den $i$-ten Polizisten bewegen möchtest.

Sobald das Spiel geendet hat, wird dein Programm durch den Server terminiert.

Beispiel-Interaktion

Ein Beispiel eines Spieles ist im folgenden Bild illustriert. Weiter unten findest du die entsprechende Kommunikation mit dem Server für Maus X und die Polizisten.

2014-1c-copsandrobbers-example.jpg?500

Beispiel-Spiel

Kommunikation Maus XKommunikation Polizisten

> X
> 2
> 100
> 7 7
> 1 2
> 1 3
> 2 4
> 3 4
> 3 5
> 5 6
> 5 7
> 3
> 6 7
< 1
> 5 5
< 2
> 3 3
< 2
> 4 1
< 4

> P
> 2
> 100
> 7 7
> 1 2
> 1 3
> 2 4
> 3 4
> 3 5
> 5 6
> 5 7
> 6 7
> 1
< 5 5
> 2
< 3 3
> 2
< 4 1

Limits

  • $1 \leq C \leq 8$
  • $10 \leq R \leq 100$
  • $10 \leq N \leq 200$
  • $10 \leq M \leq 500$

Tipps

Für interaktive Aufgaben ist es wichtig, dass du nach jeder Runde den Ausgabepuffer flushst, um sicherzustellen, dass deine Ausgabe für den Server sichtbar wird.

Benutze die folgenden Befehle:

  • C/C++: fflush(stdout);
  • C++: cout << flush;
  • Pascal: flush(output);
  • In anderen Sprachen gibt es ähnliche Befehle.

Des Weiteren ist es beim Lesen der Eingabe wichtig, dass dein Programm nicht auf mehr Zeichen wartet als der Server dir als Eingabe zur Verfügung stellt. Insbesondere Leerzeichen oder Zeilenenden in C format strings sind eine häufige Fehlerquelle. Zum Beispiel, wenn du die letzte Variable im Input mit scanf("%d ", &x); liest, wird die scanf Funktion auf das nächste Zeichen warten, das kein Leerzeichen oder Zeilenende ist. Allerdings wirst du ein solches Zeichen erst erhalten, wenn du deinen nächsten Zug bereits angegeben hast. Um dies zu lösen, benutze stattdessen scanf("%d", &x);, also keine nicht-druckbaren Zeichen nach dem %d.

Beispiel-Bots, Server und Visualisation

Während der Ersten Runde werden wir das folgende Material zur Verfügung stellen:

  • Beispiel-Bots in verschiedenen Programmiersprachen.
  • Ein Server-Programm, dass du benutzen kannst, um dein eigenes Programm gegen deines und andere Programme antreten zu lassen.
  • Eine Visualisierung, die simulierte Spiele animiert.

Du findest dieses Material hier (ZIP-File 150KB). Da es fortwährend weiterentwickelt wird, macht es Sinn, von Zeit zu Zeit auf der Website vorbeizuschauen.

Ein Update ist hier zu finden. Es enthäIt die verbesserte Visualisierung, die am SOI Tag verwended wurde, und interessantere Karten.

Bewertung

Die Bewertung der Kreativaufgabe ist anders als bei anderen Aufgaben. Du bekommst

  • 50% der Punkte für ein Programm welches das Spiel korrekt spielt, d.h. es respektiert alle Spielegeln und spielt mindestens so gut wie die Beispiel-Bots. Wichtig: Es ist nicht erlaubt, einfach den Code eines Beispiel-Bots einzuschicken. Es ist allerdings erlaubt und wird dir nahegelegt, sie als Beispiel zu verwenden, wie Eingabe und Ausgabe in deiner Programmiersprache korrekt durchgeführt wird.
  • Die restlichen 50% der Punkte werden entsprechend den Resultaten des Turniers am SOI-Tag verteilt.

Fragen?

Bei Unklarheiten oder Fragen kannst du dich gerne im Forum melden oder uns eine E-Mail schreiben unter info[ät]soi[punkt]ch.

Einsendung