Problem E
Bodenschätze

Eine erodierte Schlammwand legt neue Mineralien frei. Foto: Michael D. Turnbull, Lizenz: CC BY-SA.

Du bist für die Signalverarbeitung eines außerirdischen Bergbauunternehmens zuständig, und dein Schiff nähert sich gerade einem Asteroiden. Vorläufige Scans zeigen das Vorhandensein von $k$ Mineralvorkommen auf dem Asteroiden, aber ihre genaue Lage ist unbekannt.

Die Oberfläche des Asteroiden kann als ein Gitter aus ganzzahligen Koordinaten betrachtet werden. Jedes der Mineralvorkommen befindet sich an unbekannten ganzzahligen Koordinaten, so dass das $i$-te Vorkommen Koordinaten $(x_ i, y_ i)$ hat, wobei $-b \le x_ i \le b$ und $-b\le y_ i \le b$ für eine ganze Zahl $b$, die der Größe des ursprünglichen Scans entspricht.

Um die genaue Lage der Mineralvorkommen zu bestimmen, kannst du Sonden auf die Oberfläche des Asteroiden schicken. Die Sonden werden in Wellen von mehreren Sonden auf einmal ausgesandt.

Angenommen, du schickst eine Welle von $d$ Sonden an den Koordinaten $(s_ j,t_ j)$ für $1\leq j\leq d$ auf die Oberfläche. Wenn eine Sonde an ihren Koordinaten ankommt, bestimmt sie die Manhattandistanz zu jedem der $k$ Mineralvorkommen und sendet die Entfernungen zurück an das Schiff. Alle Datenpakete kommen gleichzeitig an, und es ist nicht möglich festzustellen, welche Sonden welche Entfernungen zurückgeschickt haben. Die Welle liefert also die $k\cdot d$ ganzzahligen Entfernungen

Minimiere die Anzahl der Sondenwellen, die an die Oberfläche geschickt werden.

Interaktion

Dies ist ein interaktives Problem. Die Interaktion beginnt damit, dass du eine einzelne Zeile mit drei ganzen Zahlen $b$, $k$ und $w$ liest: die Begrenzung des Gitters $b$, die Anzahl $k$ der Mineralvorkommen, und die maximale Anzahl $w$ der Wellen, die du senden darfst.

Du stellst dann höchstens $w$ Abfragen, die jeweils einer Welle entsprechen. Eine Abfrage besteht aus ? gefolgt von $2d$ ganzen Zahlen, die durch Leerzeichen getrennt sind, z.B. “? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$”, wobei die Anzahl $d$ der Sonden in dieser Welle die Bedingungen $1\leq d\leq 2000$ erfüllen muss. Die Werte $(s_ i,t_ i)$ werden als die Koordinaten der $i$-ten Sonde interpretiert und müssen $-10^8 \leq s_ i \leq 10^8$ und $-10^8 \leq t_ i \leq 10^8$ erfüllen. Die Antwort ist eine einzige Zeile mit $k \cdot d$ ganzen Zahlen in nicht absteigender Reihenfolge: die Manhattandistanzen zwischen allen Paaren von Mineralvorkommen und Sondenkoordinaten. Die Gesamtzahl der Sonden über alle Wellen hinweg darf den Wert $2\cdot 10^4$ nicht überschreiten.

Die Interaktion endet damit, dass du eine einzelne Zeile ausgibst, bestehend aus !, gefolgt von $k$ Punkten $x_1, y_1, x_2, y_2, \ldots x_ k, y_ k$, getrennt durch Leerzeichen. Dies muss die letzte Zeile der Ausgabe sein.

Deine Eingabe gilt als korrekt, wenn du alle Standorte der Mineralvorkommen ausgibst. Du kannst sie in beliebiger Reihenfolge ausgeben.

Beschränkungen und Bewertung

Es gilt immer $1\leq b \leq 10^8$, $1 \leq k \leq 20$, und $2 \le w \le 10^4$.

Deine Lösung wird an einer Reihe von Testgruppen getestet, von denen jede eine bestimmte Anzahl von Punkten wert ist. Jede Testgruppe enthält eine Reihe von Testfällen. Um die Punkte für eine Testgruppe zu erhalten, musst du alle Testfälle in der Testgruppe lösen. Deine endgültige Punktzahl ist die maximale Punktzahl für eine einzelne Einsendung.

Beispiel

In diesem Beispiel gibt es $k=2$ Mineralvorkommen an den Positionen $(1,2)$ und $(-3,-2)$, dargestellt als rote Sterne. In der ersten Welle könntest du $d=3$ Sonden zu den Positionen $(-4,-3)$, $(-1, 0)$ und $(2,-1)$ schicken, die als schwarze Punkte dargestellt sind. Diese Welle würde die folgenden $6$ Entfernungen zurückgeben:

In der nächsten Welle könntest du $d=2$ Sonden nach $(1,2)$ und $(0,-2)$ schicken. Diese Welle würde die folgenden $4$ Entfernungen zurückgeben:

 4 2 10

 ? -4 -3 -1 0 2 -1

 2 4 4 4 6 10

 ? 1 2 0 -2

 0 3 5 8

 ! 1 2 -3 -2