Problem E
Wurmprobleme
Languages
de
en
et
is
lt
lv
no
pl
ru
sv
Du möchtest einen Platz in der Erde für deinen Wurm Maximus finden. Die Suche begrenzt du auf ein quaderförmiges Gebiet der Größe $N \times M \times K$ Zentimeter, welches du in ein dreidimensionales Raster von einem Kubikzentimeter großen Zellen eingeteilt hast, die durch ihre Position $(x,y,z)$ im Gitter beschrieben werden ($1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$). Jede Zelle hat eine gewisse Feuchtigkeit $H[x,y,z]$, welche eine ganze Zahl im Bereich $1 \dots 10^9$ ist. Du kannst die Feuchtigkeit einer Zelle mit einem besonderen Sensor bestimmen.
Maximus liebt feuchte Gebiete. Daher musst du ihn in eine Zelle setzen, die mindestens so feucht ist wie ihre Nachbarzellen. Ansonsten würde er weggehen und du würdest Schwierigkeiten haben, ihn wiederzufinden. Anders ausgedrückt musst du ihn in einem lokalem Feuchtigkeitsmaximum platzieren. Genauer gesagt, finde eine Zelle $(x,y,z)$ mit
\[ H[x,y,z] \ge \max (H[x+1,y,z], H[x-1,y,z], H[x,y+1,z], H[x,y-1,z], H[x,y,z+1], H[x,y,z-1]), \]wobei Zellen außerhalb des Quaders den Wert $0$ haben (weil Maximus unbedingt im Quader bleiben will).
Allerdings kann die Anzahl an Zellen sehr groß werden, also möchtest du nicht die Feuchtigkeit aller Zellen messen. Deshalb interagierst du mit dem Grader, und fragst nach der Feuchtigkeit an bestimmten Punkten. Wenn du eine geeignete Position für Maximus gefunden hast, gib diese aus.
Interaktivität
Die erste Zeile des Inputs enthält vier positive ganze Zahlen: $N$, $M$, $K$ und $Q$, wobei $N$, $M$ und $K$ die Dimensionen des Quaders angeben und $Q$ die maximale Anzahl der Messungen ist, die du ausführen darfst.
Danach kannst du bis zu $Q$ Zeilen der Form “? x y z” auf der Standardausgabe ausgeben. Dadurch fragst du den Grader nach der Feuchtigkeit am Punkt $(x, y, z)$. Jede dieser Zeilen wird der Grader mit einer Zeile mit der ganzen Zahl $H[x,y,z]$ beantworten, die du über die Standardeingabe einlesen kannst.
Danach muss dein Programm genau eine Zeile der Form “! x y z” ausgeben. Dadurch behauptest du, dass der Punkt $(x, y, z)$ ein nach dem obigen Kriterium geeigneter Ort für Maximus ist. Der Grader wird auf diese Ausgabe nicht antworten.
Alle Werte von $x, y, z$ müssen $1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$ erfüllen. Falls sie dies nicht tun, oder falls eine Zeile der Ausgabe ein ungültiges Format hat, oder falls du mehr als $Q$ Anfragen stellst, wird der Grader mit -1 antworten und sich beenden. Falls dies passiert, sollte dein Programm sich auch beenden. Falls es weiterläuft, bekommt es eventuell fälschlicherweise die Bewertung Runtime Error oder Time Limit Exceeded.
Du musst die Standardausgabe flushen, bevor du die Antwort des Graders einliest. Ansonsten bekommt dein Programm die Bewertung Time Limit Exceeded. Du kannst die folgenden Befehle nutzen:
-
Java: System.out.println() flusht automatisch.
-
Python: print() flusht automatisch.
-
C++: cout << endl; flusht und schreibt zusätzlich einen Zeilenumbruch. Falls du printf nutzt: fflush(stdout).
-
Pascal: Flush(Output).
Um bei dieser Interaktion zu helfen, stellen wir Hilfscode zur Verfügung, den du in dein Programm kopieren darfst. Einen Link zu diesem Code für alle unterstützten Sprachen (C++, Pascal, Java, Python) kann in der Seitenleiste der Kattis-Aufgabenseite gefunden werden. Der Hilfscode nutzt auch schnelle Eingabe/Ausgabe-Methoden, die für Python und Java hilfreich sein können (nur für die letzten beiden Testgruppen relevant).
Der Grader ist nicht adaptiv; jeder Testfall hat eine festgelegte Verteilung von Feuchtigkeitswerten, die nicht von den Anfragen des Programms abhängt.
Beschränkungen
Deine Lösung wird auf mehreren Testgruppen ausgeführt werden, von denen jede eine bestimmte Punktzahl wert ist. Jede Testgruppe enthält mehrere Testcases. Um Punkte für eine Testgruppe zu bekommen, müssen alle Testfälle in der entsprechenden Gruppe gelöst werden. Deine finale Punktzahl wird die maximal erreichte Punktzahl in einer einzelnen Einsendungen sein.
|
Gruppe |
Punkte |
Limits |
|
1 |
10 |
$M = K = 1$, $N = 1\, 000\, 000$, $Q = 10\, 000$ |
|
2 |
22 |
$M = K = 1$, $N = 1\, 000\, 000$, $Q = 35$ |
|
3 |
12 |
$K = 1$, $N = M = 200$, $Q = 4\, 000$ |
|
4 |
19 |
$K = 1$, $N = M = 1\, 000$, $Q = 3\, 500$ |
|
5 |
14 |
$N = M = K = 100$, $Q = 100\, 000$ |
|
6 |
23 |
$N = M = K = 500$, $Q = 150\, 000$ |
Beispielinteraktion
In Beispiel 1 hat der Quader die Größe $3\times 1\times 1$ und die Feuchtigkeit in den drei Zellen ist {10, 14, 13}. Unten findest du eine Beispielinteraktion, wobei die mit JUDGE beginnenden Zeilen die Ausgabe des Graders (also die Eingabe deines Programms) und die mit YOU beginnenden Zeilen die Ausgabe deines Programms sind.
Da $14$ größer oder gleich den benachbarten Werten ($10$ und $13$) ist, ist die Position $(2,1,1)$ ein geeigneter Ort für Maximus. Es wurden 3 Anfragen gestellt, was der maximal erlaubten Anzahl entspricht ($Q=3$). Daher wird dieser dialog auf dem Beispiel mit Accepted bewertet.
JUDGE: 3 1 1 3 YOU: ? 3 1 1 JUDGE: 13 YOU: ? 2 1 1 JUDGE: 14 YOU: ? 1 1 1 JUDGE: 10 YOU: ! 2 1 1
