Problem B
Wettstarren

Ein Wettstarren ist ein klassischer Kampf der Unerschütterlichkeit, bei dem zwei Personen einander in die Augen starren und dabei einen Gesichtsausdruck von sicherer Gelassenheit bewahren. Ziel ist es, den Augenkontakt länger aufrechtzuerhalten als der Gegner. Der Wettbewerb endet, wenn einer der Teilnehmer die Fassung verliert, indem er wegschaut, lächelt, spricht oder kichert.

Als Trainer des nationalen Anstarrwettbewerbs musst du für das bevorstehende Weltfinale die Unerschütterlichkeit aller $n$ Mitglieder deiner Mannschaft bestimmen. Der $i$-te Sportler kann den Blickkontakt genau $a_ i$ Sekunden lang aufrechterhalten, aber diese Werte sind Dir anfangs unbekannt. Du könntest zum Beispiel eine Mannschaft mit $n=3$ Mitgliedern haben:

Wenn die Athleten $i$ und $j$ gegeneinander antreten, dauert die Konfrontation genau $\min (a_ i, a_ j)$ Sekunden, wonach der schwächere Teilnehmer die Fassung verliert und beide Teilnehmer innerhalb eines Sekundenbruchteils zu lächeln und zu kichern beginnen. Wenn zum Beispiel Anna gegen Esther antritt, dauert der Wettbewerb $431$ Sekunden. Für einen außenstehenden Beobachter ist es unmöglich, den tatsächlichen Gewinner der Konfrontation (in diesem Fall Esther) zu bestimmen, nur die Dauer des Wettkampfs ist messbar.

Dein Ziel ist es, die Werte $a_1,\ldots , a_ n$ anhand möglichst weniger Wettkämpfe zu schätzen. Es ist klar, dass die Stärke des stärksten Athleten nie bestimmt werden kann, also darfst du einen der Werte $a_ i$ unterschätzen.

Interaktion

Dies ist ein interaktives Problem. Die Interaktion beginnt damit, dass du eine einzelne Zeile einliest, die die ganze Zahl $n$ enthält. Du kannst dann Abfragen der Form “? $i$ $j$” stellen, wobei $1\leq i\leq n$ und $1\leq j\leq n$ und $i\neq j$ gelten muss. Die Antwort auf eine Abfrage ist eine einzelne ganze Zahl: der Wert $\min (a_ i, a_ j)$. Die Interaktion endet damit, dass du eine einzelne Zeile ausgibst, bestehend aus !, gefolgt von $n$ Schätzungen in Form von ganzen Zahlen $b_1$, $\ldots $, $b_ n$, getrennt durch Leerzeichen. Dies muss die letzte Zeile der Ausgabe sein.

Deine Einsendung ist korrekt, wenn $b_ i=a_ i$ für jeden Teilnehmer $i$ außer einem, den du vielleicht unterschätzt, gilt. Um genau zu sein: Wir verlangen $b_ i\leq a_ i$ für alle $1\leq i\leq n$ und erlauben $b_ k \neq a_ k$ für höchstens ein $k$.

Der Interaktor ist nicht adaptiv, das heißt die $a_1,\ldots , a_ n$ werden bestimmt, bevor die Interaktion beginnt.

Beschränkungen und Bewertung

Die Anzahl $n$ der Athleten erfüllt $2\leq n\leq 1500$. Die Unerschütterlichkeit $a_ i$ eines jeden Athleten erfüllt $1\leq a_ i\leq 86\, 400$; sie sind alle unterschiedlich. Du kannst höchstens $3000$ Abfragen machen; Deine letzte Ausgabezeile, d.h. die Zeile, die mit ! beginnt, wird nicht als Abfrage gezählt.

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.

Für Gruppe $3$ ist deine Punktzahl die niedrigste Punktzahl aller Testfälle in der Gruppe. Die Punktzahl für jeden Testfall hängt von der Anzahl der Abfragen ab, die du verwendest; weniger Abfragen sind besser. Angenommen, du verwendest $q$ Abfragen. Wenn $q \le n+25$, dann bekommst du die vollen $80$ Punkte. Wenn $q > 3000$ ist, bekommst du keine Punkte. Andernfalls bekommst du $118{,}2 - 12 \cdot \ln (q - n)$ Punkte, gerundet auf die nächste ganze Zahl. Für $n = 1500$ und $q = 3000$ bekommst du zum Beispiel $30$ Punkte.

Erklärung der Beispielinteraktion

Beispielinteraktion $1$ zeigt eine mögliche Interaktion anhand des obigen Beispiels. Beachte, dass Annas und Tonys Stärken korrekt bestimmt sind. (Esthers Stärke kann nie bestimmt werden.)

3

? 1 2

431

? 1 3

121

? 3 2

121

! 431 431 121