---
title: Hamilton
---

Betrachten wir einen gerichteten Graphen mit $n$ Knoten, die mit $1, 2, \dots, n$ nummeriert sind. Der Graph wird als _Turnier_ bezeichnet, wenn zwischen allen Knotenpaaren genau eine Kante in eine beliebige Richtung besteht. Das heißt, für jedes Paar unterschiedlicher Knoten $u$ und $v$ gibt es entweder eine Kante von $u$ nach $v$ oder von $v$ nach $u$.

Ein Hamiltonkreis ist eine Folge $c_1, c_2, \dots, c_n$, die alle Knoten besucht und zum Start zurückkehrt, wobei sie den Kanten im Graphen folgt. Für alle $1 \le i \le n-1$ muss es eine Kante von $c_i$ nach $c_{i+1}$ geben. Zusätzlich muss es eine Kante von $c_n$ nach $c_1$ geben.
 
Du darfst einen Turniergraphen mit $n$ Knoten frei konstruieren. Die Nummerierung der Knoten wird anschließend beliebig permutiert. Kannst du durch Abfragen der Kantenrichtungen im permutierten Graphen einen Hamiltonkreis finden?

# Interaktion

Dies ist eine interaktive Aufgabe. Zu Beginn liest du zwei ganze Zahlen $n$ und $t$ ein: die Anzahl der Knoten und die Anzahl der Testfälle.

Gib anschließend $n$ Zeilen aus, um den Turniergraphen zu beschreiben. Gib in der $u$-ten dieser Zeilen $n$ Zeichen „`0`“ oder „`1`“ aus. Ein Zeichen „`1`“ an Position $v$ bedeutet, dass es eine Kante von $u$ nach $v$ gibt. Es darf keine Kante von $u$ zu sich selbst geben.

Anschließend folgen $t$ Testfälle. Jeder Testfall verwendet denselben von dir bereitgestellten Graphen, jedoch wird die Nummerierung vom Grader geändert und geheim gehalten. Du darfst eine bestimmte Anzahl von Abfragen stellen, nach denen du einen Hamiltonkreis ausgeben sollst.

Um eine Abfrage zu stellen, gib „`?` $u$ $v$“ aus, wobei $1 \le u,v \le n$ verschiedene Knoten im permutierten Graphen sind. Der Grader antwortet entweder mit „`>`“, wenn die Kante von $u$ nach $v$ verläuft, oder mit „`<`“, wenn die Kante von $v$ nach $u$ verläuft.

Wenn du einen Hamiltonzyklus gefunden hast, gib „`!`“ gefolgt von $n$ ganzen Zahlen $c_1, c_2, \dots, c_n$ aus. Beachte, dass die Zahlen $c_i$ der permutierten Nummerierung folgen sollten. Der nächste Testfall beginnt unmittelbar nachdem du die Antwort ausgegeben hast.

Ein Testskript kann [hier](files/hamilton-test.py) heruntergeladen werden. Am Anfang des Skripts findest du eine Anleitung zur Verwendung. 

# Beschränkungen

- $4 \le n \le 500$
- $1 \le t \le 200$

# Beispielinteraktion

```
5 2

01110
00101
00010
01001
10100

? 1 2
>
? 2 3
>
? 3 4
>
? 4 5
>
? 5 1
>
! 1 2 3 4 5

? 1 2
<
? 1 5
>
? 4 3
>
? 4 5
<
? 3 2
>
! 1 5 4 3 2
```

_Erklärung_: Im ersten Testfall sind die Knotennummerierungen unverändert. Dabei bildet $1,2,3,4,5$ einen Hamiltonkreis.

Im zweiten Testfall wurden die Knotennummerierungen zu $2,4,1,5,3$ in dieser Reihenfolge permutiert. Die Folge $1,5,4,3,2$ ist ein Hamiltonkreis, da $3,4,2,5,1$ im ursprünglichen Graphen ein Hamiltonkreis war.

In der folgenden Abbildung ist links der ursprüngliche Graph und rechts der permutierte Graph aus dem zweiten Testfall dargestellt. Die beiden Hamiltonkreise sind rot hervorgehoben.

![Beispielabbildung](files/example.svg "=420x")

# Bewertung

In jeder Teilaufgabe gibt es nur eine Testeingabe mit $t = 200$ Testfällen. In jedem Testfall wird die Nummerierung des Graphen gleichverteilt zufällig permutiert. Werden in einem einzelnen Testfall mehr als $10^4$ Abfragen durchgeführt, führt dies zur Bewertung „WRONG ANSWER“.

Sei $Q$ die durchschnittliche Anzahl der Abfragen, die dein Programm in allen zu einer Teilaufgabe gehörenden Testfällen durchführt. Du erhältst Punkte für die Teilaufgabe, wenn $Q$ nicht größer als die angegebene Grenze ist.

| Teilaufgabe | Beschränkungen | Punkte    |
| :-----: | ----------- | :-------: |
| 1       | $n = 4, Q \le 12$ | [score=1] |
| 2       | $n = 50, Q \le 1225$ | [score=2] |
| 3       | $n = 50, Q \le 300$ | [score=3] |
| 4       | $n = 500, Q \le 1500$ | 1&ndash;76 |

In Teilaufgabe 4 wird deine Punktzahl nach der folgenden Formel berechnet:

$$
\left\lfloor \frac {25\,000} {\max(750, Q) - 500} - 24 \right\rfloor
$$

Wenn zum Beispiel die durchschnittliche Anzahl an Abfragen deines Programms $Q=1500$ ist, erhältst du 1 Punkt für die Teilaufgabe. Wenn $Q=1000$, erhältst du 26 Punkte, und wenn $Q=750$, erhältst du 76 Punkte.
