Swiss Olympiad in Informatics

Timon Gehr hat die bei Grand Theft Cake gewonnen.

Nach dem unglücklichen Zwischenfall im Aperture Science Enrichment Center hast du das überaus praktische Portal-Gerät für spätere Nutzung zur Seite gelegt - man weiss ja nie. Seit deinem letzten Besuch ist dein Hunger nach dem leckeren Kuchen ungestillt. Mmmh, lecker! Weil du ihn beim letzten Mal nicht gefunden hast, muss der Kuchen immer noch irgendwo in den verschütteten Gängen der Aperture Science Laboratories versteckt sein…

In dieser Aufgabe sollst du durch die unterirdischen Gäge und Räume navigieren, den versprochenen Kuchen finden und zur Startposition zurückkehren. Das Spiel wird in zwei Dimensionen gespielt, aus der Vogelperspektive. Die Spielfigur kann die folgenden Aktionen ausführen:

• Look - In eine Richtung schauen (Rückmeldung: Distanz zur nächsten Wand) [0.1 Sekunden]
• Walk - In eine Richtung gehen (auf dem direkten Weg) [Distanz in Sekunden]
• Shoot - Portal A oder B platzieren (Das Portall wird auf der nächsten Wand erstellt) [5 Sekunden]
• Teleport - Vom einen Portal zum anderen Teleportieren (benutzt das nähere Portal) [keine Kosten]

Das Portal-Gerät schiesst ein Portal des Typs A oder B in eine beliebige Richtung. Erstellt wird dieses, sobald die Linie auf die nächste Wand trifft. Um das erstellte Portal anschliessend zu benutzen, musst du auf die Nähe von maximal 1 Einheit herangehen und den Befehl Teleport verwenden. Die Spielfigur wird dann an die Position des jeweils anderen Portals bewegt (sofern dieses bereits erstellt wurde).

Zu beachten ist, dass du in jede beliebige Richtung schauen, schiessen und gehen kannst! Jede der obenstehenden Aktionen kostet die notierte Menge Spielzeit. Du sollst den Kuchen in möglichst kurzer Zeit finden und zurückbringen. Um auch anreize für schnelle Programme zu schaffen, werden wir die Laufzeit deines Programms mit einem Faktor¹⁾ multiplizieren und dann zur Spielzeit addieren.

Die gesamte Interaktion mit dem Server ist textbasiert. Für die verständigung ist es wichtig, dass du nach deinem Output den entsprechenden flush befehl deiner Sprache benutzt, um das Zwischenspeichern zu verhindern (Sonst wartet der Server vergeben auf deinen Befehl). Für das Spiel stehen dir die folgenden Kommandos zur Verfügung:

Alle Zahlen in dieser Aufgabe sind Fliesskommazahlen (float). Die vom Server zurückgegebenen Koordinaten sind immer mit einer Genauigkeit von drei Kommastellen. Du musst den Ort eines Portals (zum Teleportieren) nicht genau treffen - sofern du näher als 1 Einheit vom Ziel stehst, wird der Server automatisch annehmen, dass du dort hin wolltest (und die fehlende Gehdistanz addieren).

Alle Winkelangaben sind in Grad im Bereich [0-360). Wir halten uns an die Konvention, dass 0 Grad der positiven x-Achse (=rechts=Osten) entspricht, während die 90 Grad Richtung für positives y (=oben=Norden) steht.

Du kannst nur zwei verschiedene Portale platzieren: A und B. Sobald du ein neues Portal vom Typ A platzierst, wird das bisherige Portal A entfernt, sodass von jedem Typ immer maximal eines auf dem Spielfeld ist. Mit dem Befehl Teleport wirst du durch das nahegelegene Portal zum jeweils anderen teleportiert. (Um den Befehl zu benutzen musst du näher als 1 Einheit vom Ausgansportal stehen.)

Falls du beim Bewegen in eine Wand läufst, wird der Server den Befehl sofort abbrechen. Deine resultierende Position ist der Ort der Kollision mit der Wand, von dort kannst du dich dann weiterbewegen. Auch das benutzen des Befehls Teleport wird einfach ignoriert, falls sich kein Portal in der Nähe befindet (oder das zweite noch nicht platziert sein sollte). Als Rückgabewert gibt der Server deine alte Position x y.

Der Kuchen ist ein Kreis mit Radius 1 Einheit. Du musst innerhalb dieses Kreises treten, um den Kuchen aufzulesen, und anschliessend zum Startpunkt zurückkehren. Zu beachten gilt, dass Portale beim Platzieren den Kuchen durchdringen (und auf die Wand dahinter treffen). Du kannst den Kuchen also nur mit dem Befehl Look aufspüren.

Um den Kuchen aufzulesen, musst du innerhalb des Kreises stehen am Ende eines Walk oder Teleport Befehls. Du kannst mit einem Look Befehl prüfen, ob du wirklich im innern des Kuchenkreises stehst: Dieser gibt die Rückmeldung Cake 0.000 bei erfolgreichem Auflesen.

Die folgenden Zeilen zeigen eine mögliche Interaktion mitt dem Server:

<< Position
>> 0.000 0.000
<< Look 0.0
>> Wall 1.500
<< Look 90.0
>> Wall 8.700
<< Shoot 0.0 A
>> 1.500 0.000
<< Shoot 90.0 B
>> 0.000 8.700
<< Walk 0.0 1.5
>> 1.500 0.000
<< Teleport
>> 0.000 8.700
<< Look 0.0
>> Cake 2.000
<< Walk 0.0 2.0
>> 2.000 8.700
<< Walk 180.0 2.0
>> 0.000 8.700
<< Teleport
>> 1.500 0.000
<< Walk 180.0 1.5
>> 0.000 0.000

Im obenstehenden Beispiel schaut der Spieler zunächst nach Osten und Norden (positive x und y Richtung), schliesst anschliessend ein Portal in beide Richtungen, betritt das Portal im Osten, findet den Kuchen auf der anderen Seite und kehrt wiederum durch das Portal zurück. Falls dein Browser animierte gif's unterstützt kannst du eine Visualisierung des Ablaufs auf der rechten Seite sehen. (Natürlich müsste ein echter Spieler zunächst herausfinden, wo sich der Kuchen befindet.)

• Alle Koordinaten sind im Bereich [-500, 500].
• Der Spieler hat keine Ausdehnung und kann sich durch jede Öffnung, sowie beliebig nahe an Objekten bewegen.
• Du solltest immer die Koordinaten in der Serverantwort als deine jetzige Position verwenden, ansonsten können sich Rundungsfehler akkumulieren.
• Die Levels werden so gezeichnet, dass sich keine scharfen Ecken bilden und Gänge im Allgemeinen eine Breite von drei oder mehr Einheiten haben (Aus geschlossenen Polygonen oder Kurven).
• Im Prinzip ist es möglich nur mit den Richtungen N,W,S,O und Einheitschritten zu spielen (allerdings ist dies nicht sehr effizient).
• Es kann auch mehr als ein Kuchenstück geben - in diesem Fall musst du nur ein (beliebiges) auflesen.
• Die effektiven Kosten der verschiedenen Aktionen können im Verlauf der ersten Runde noch (wenig) angepasst werden: Schreibe also dein Programm so, dass du diese Anpassung einfach vornehmen kannst.
• Mit dem Testserver kannst du dein Programm lokal testen.