---
title: Hamiltons
---

Apskatīsim orientētu grafu ar $n$ virsotnēm, kas numurētas ar $1,2,\dots,n$. Grafs tiek saukts par _turnīru_, ja starp visiem virsotņu pāriem ir tieši viena šķautne vienā vai otrā virzienā. Tas ir, jebkuram atšķirīgu virsotņu pārim $u$ un $v$ ir vai nu šķautne no $u$ uz $v$, vai no $v$ uz $u$.

Hamiltona cikls ir secība $c_1, c_2, \dots, c_n$, kas apmeklē visas virsotnes un atgriežas sākuma punktā, sekojot grafa šķautnēm. Visiem $1 \le i \le n-1$, jābūt šķautnei no $c_i$ uz $c_{i+1}$. Papildus tam, jābūt šķautnei no $c_n$ uz $c_1$.

Jūs varat brīvi konstruēt turnīru grafu ar $n$ virsotnēm. Virsotņu numerācija pēc tam tiek sajaukta. Vai, veicot vaicājumus par šķautņu virzieniem sajauktajā grafā, varat atrast Hamiltona ciklu?

# Komunikācija

Šis ir interaktīvs uzdevums. Jūsu programmai, sākot darbu, ir jāievada divi veseli skaitļi $n$ un $t$, kas attiecīgi apzīmē virsotņu skaitu un testu skaitu.

Pēc tam ir nepieciešams izdrukāt $n$ rindas, kas raksturo turnīra grafiku. Katra $u$-tā rinda satur $n$ rakstzīmes, kas var būt vai nu "`0`", vai "`1`". Rakstzīme "`1`" pozīcijā $v$ norāda, ka pastāv šķautne no $u$ uz $v$.
Nedrīkst būt šķautne no virsotnes uz sevi pašu.

Tālāk seko $t$ testi. Katrs tests izmanto to pašu grafu, kuru jūs sākotnēji definējāt, taču virsotņu numerācija ir sajaukta, un vērtētājs to tur slepenībā. Jūs varat uzdot vaicājumus, pēc kuriem jums jāziņo par Hamiltona ciklu.

Lai veikt vaicājumu, izdrukājiet "`?` $u$ $v$", kur $1 \le u,v \le n$ ir dažādas virsotnes sajauktajā grafā. Vērtētājs atbild ar "`>`", ja pastāv šķautne no $u$ uz $v$, vai "`<`", ja pastāv šķautne no $v$ uz $u$.

Kad esat noteicis Hamiltona ciklu, izdrukājiet "`!`", kam seko $n$ veseli skaitļi $c_1, c_2, \dots, c_n$. Šiem skaitļiem ir jāatbilst sajauktajai numerācijai. Pēc atbildes izdrukāšanas uzreiz sākas nākamais testa gadījums.

Testēšanas skriptu var lejupielādēt [šeit](files/hamilton-test.py). Skripta sākumā ir iekļauti norādījumi par tā lietošanu.

# Ierobežojumi

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

# Komunikācijas piemērs

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

_Paskaidrojums:_ Pirmajā testā virsotnes ir sakārtotas sākotnējā secībā, tāpēc $1,2,3,4,5$ ir Hamiltona cikls.

Otrajā gadījumā virsotņu numuri $1,2,3,4,5$ tiek samainīti uz $2,4,1,5,3$ šādā secībā. Secība $1,5,4,3,2$ patiešām ir Hamiltona cikls, jo $3,4,2,5,1$ bija tāds sākotnējā grafā.

Attēlā pa kreisi ir redzams sākotnējais grafs, bet pa labi ir redzams sajauktais grafs no otrā testa gadījuma. Abi Hamiltona cikli ir izcelti sarkanā krāsā.

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

# Vērtēšana

Katrā apakšuzdevumā ir tikai viena testa ievaddati, ar $t = 200$ testiem. Katrā testā grafa numerācija tiek sajaukta nejaušā kārtībā. Veicot vairāk nekā $10^4$ vaicājumu vienā testā, tiek iegūts vērtējums WRONG ANSWER.

Ar $Q$ apzīmēsim vidējo vaicājumu skaitu, ko veic jūsu programma pār visiem testiem, kas pieder apakšuzdevumam. Jūs saņemat punktus par apakšuzdevumu, ja $Q$ nav lielāks par norādīto robežu.

| Apakšuzdevums | Ierobežojumi | Punkti    |
| :-----: | ----------- | :-------: |
| 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 |

Apakšuzdevumā 4 punktus saņem pēc šādas formulas:

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

Piemēram, ja jūsu programmas veikto vaicājumu vidējais skaits ir $Q=1500$, jūs iegūstat 1 punktu no apakšuzdevuma. Ja $Q=1000$, jūs iegūstat 26 punktu, un, ja $Q=750$, jūs iegūstat 76 punktus.
