---
title: Hamilton
---

Vaatleme $n$ tipuga suunatud graafi, mille tipud on nummerdatud $1, 2, \dots, n$. Kutsume graafi _turniiriks_, kui iga paari tippude vahel leidub täpselt üks serv (kas ühes või teises suunas). See tähendab, et iga erinevate tippude paari $u$ ja $v$ jaoks leidub kas serv tipust $u$ tippu $v$ või serv tipust $v$ tippu $u$.

Hamiltoni tsükkel on jada $c_1, c_2, \dots, c_n$, mis külastab kõiki tippe ja jõuab tagasi algusesse, järgides graafi servi. Iga $1 \le i \le n-1$ jaoks peab leiduma serv tipust $c_i$ tippu $c_{i+1}$. Lisaks peab leiduma serv tipust $c_n$ tippu $c_1$.

Võid konstrueerida suvalise turniiri, mis koosneb $n$ tipust. Seejärel tippude nummerdus segatakse suvaliselt. Kas suudad leida Hamiltoni tsükli, tehes päringuid servade suundade kohta segatud graafis?

# Suhtlus

See on interaktiivne ülesanne. Esiteks loe kaks täisarvu $n$ ja $t$: vastavalt tippude arv ja testjuhtude arv.

Järgmiseks väljasta $n$ rida, mis kirjeldavad turniiri graafi. Nendest ridadest $u$-ndale väljasta $n$ tähemärki "`0`" või "`1`". Tähemärk "`1`" positsioonil $v$ tähendab, et leidub serv tipust $u$ tippu $v$. Graafis ei tohiks olla ühtegi serva tipust $u$ iseendasse.

Järgnevad $t$ testjuhtu. Iga testjuht kasutab sama graafi, kuid nummerdus on segatud ja salajane. Sa võid teha mingi arvu päringud ja pärast seda väljastada Hamiltoni tsükli.

Päringu tegemiseks väljasta "`?` $u$ $v$", kus $1 \le u, v \le n$ on erinevad tipud segatud graafis. Hindamisprogramm vastab kas tähemärgiga "`>`", kui serv on tipust $u$ tippu $v$, või märgiga "`<`", kui serv on tipust $v$ tippu $u$.

Kui oled Hamiltoni tsükli leidnud, siis väljasta "`!`", millele järgnevad $n$ täisarvu $c_1, c_2, \dots, c_n$. Pane tähele, et arvud $c_i$ peavad järgima segatud nummerdust. Järgmine testjuht algab koheselt pärast seda, kui oled vastuse väljastanud.

Saadaval on ka [testimisskript](files/hamilton-test.py). Skripti alguses on toodud kasutusjuhised.

# Piirangud

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

# Näidissuhtlus

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

_Selgitus:_ Esimeses testjuhus juhtuvad tipud olema täpselt originaalses järjekorras, seega $1,2,3,4,5$ on Hamiltoni tsükkel.

Teises testjuhus segatakse tippude numbrid $1,2,3,4,5$ numbriteks $2,4,1,5,3$ selles järjekorras. Jada $1,5,4,3,2$ on tõepoolest Hamiltoni tsükkel, kuna $3,4,2,5,1$ oli algses graafis Hamiltoni tsükkel.

Järgneval joonisel on vasakul kujutatud algne graaf ja paremal teise testjuhu segatud graaf. Kaks Hamiltoni tsüklit on tähistatud punasega.

![Näidise joonis](files/example.svg "=420x")

# Hindamine

Igas alamülesandes on vaid üks testsisend, milles on $t = 200$ testjuhtu. Igas testjuhus on graafi nummerdus segatud ühtlase jaotusega. Ühes testjuhus rohkem kui $10^4$ päringu sooritamine annab lahenduse tulemuseks WRONG ANSWER.

Olgu $Q$ programmi poolt tehtud keskmine päringute arv üle kõigi antud alamülesandesse kuuluvate testjuhtude. Alamülesande eest saab punkte, kui $Q$ on ülimalt antud piirang.


| Alamülesanne | Piirangud | 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 |

Viimase alamülesande eest saab punkte vastavalt järgnevale valemile:

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

Näiteks kui lahenduse tehtud keskmine päringute arv on $Q=1500$, siis saab viimasest alamülesandest 1 punkti. Kui $Q = 1000$, siis saab 26 punkti, ja kui $Q = 750$, siis saab 76 punkti.
