---
title: Hamilton
---

Verkossa on $n$ solmua, jotka on numeroitu $1,2,\dots,n$. Verkkoa kutsutaan _turnausverkoksi_, jos jokaisen solmuparin välillä on tasan yksi kaari jompaankumpaan suuntaan. Toisin sanoen kun valitaan mitkä tahansa kaksi eri solmua $u$ ja $v$, verkossa on joko kaari solmusta $u$ solmuun $v$ tai solmusta $v$ solmuun $u$.

Hamiltonin kierros on jono $c_1, c_2, \dots, c_n$, joka käy läpi kaikki solmut ja palaa takaisin alkuun verkon kaaria seuraten. Verkossa tulee olla kaari solmusta $c_i$ solmuun $c_{i+1}$, kun $1 \le i \le n-1$. Lisäksi verkossa tulee olla kaari solmusta $c_n$ solmuun $c_1$.

Voit rakentaa haluamallasi tavalla turnausverkon, jossa on $n$ solmua. Tämän jälkeen solmujen numerointi sekoitetaan. Pystytkö löytämään Hamiltonin kierroksen kyselemällä kaarten suuntia sekoitetussa verkossa?

# Interaktio

Tämä on interaktiivinen tehtävä. Lue ensin kaksi kokonaislukua $n$ ja $t$: solmujen määrä ja testitapausten määrä.

Tulosta sitten $n$ riviä, jotka kuvaavat turnausverkon. Rivillä $u$ tulee olla $n$ merkkiä, joista jokainen on "`0`" tai "`1`". Merkki "`1`" kohdassa $v$ tarkoittaa, että verkossa on kaari solmusta $u$ solmuun $v$. Verkossa ei tule olla kaarta solmusta $u$ itseensä.

Sitten tulee $t$ testitapausta. Jokainen testitapaus käyttää antamaasi verkkoa, mutta numerointi on sekoitettu eikä arvostelija kerro sitä. Voit tehdä jonkin määrän kyselyjä, minkä jälkeen sinun tulee ilmoittaa Hamiltonin kierros.

Voit tehdä kyselyn tulostamalla "`?` $u$ $v$", missä $1 \le u,v \le n$ ovat kaksi eri solmua sekoitetussa verkossa. Arvostelija vastaa joko "`>`", jos kaari on solmusta $u$ solmuun $v$, tai "`<`", jos kaari on solmusta $v$ solmuun $u$.

Kun olet löytänyt Hamiltonin kierroksen, tulosta "`!`" ja sen jälkeen $n$ kokonaislukua $c_1, c_2, \dots, c_n$. Huomaa, että lukujen $c_i$ tulee vastata sekoitettua numerointia. Seuraava testitapaus alkaa heti sen jälkeen, kun olet tulostanut vastauksen.

Voit ladata testausskriptin [tästä](files/hamilton-test.py). Skriptin alussa on sen käyttöohjeet.

# Rajat

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

# Esimerkki-interaktio

```
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
```

_Selitys_: Ensimmäisessä testitapauksessa solmujen sekoitettu järjestys sattuu olemaan sama kuin alkuperäinen järjestys, minkä takia $1,2,3,4,5$ on Hamiltonin kierros.

Toisessa tapauksessa solmujen tunnukset $1,2,3,4,5$ on sekoitettu järjestykseen $2,4,1,5,3$. Jono $1,5,4,3,2$ on Hamiltonin kierros, koska jono $3,4,2,5,1$ on Hamiltonin kierros alkuperäisessä verkossa.

Alla olevasssa kuvassa vasemmalla on alkuperäinen verkko ja oikealla on toisen testitapauksen sekoitettu verkko. Kaksi Hamiltonin kierrosta on esitetty punaisella värillä.

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

# Pisteytys

Jokaisessa osatehtävässä on vain yksi testisyöte, jossa on $t = 200$ testitapausta. Jokaisessa tapauksessa verkon solmut on sekoitettu satunnaisesti tasajakauman mukaisesti. Jos teet yhden testitapauksen aikana yli $10^4$ kyselyä, saat tuloksen WRONG ANSWER.

Merkitään $Q$:llä keskimääräistä ohjelmasi tekemää kyselyjen määrää kaikissa tietyn osatehtävän testitapauksissa. Saat osatehtävästä pisteitä, jos $Q$ ei ole annettua rajaa suurempi.

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 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 |

Osatehtävässä 4 pistemääräsi lasketaan seuraavalla kaavalla:

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

Esimerkiksi jos ohjelmasi tekee keskimäärin $Q=1500$ kyselyä, saat yhden pisteen osatehtävästä. Jos $Q=1000$, saat 26 pistettä, ja jos $Q=750$, saat 76 pistettä.
