---
title: Hamilton
---

Skoðum áttað net með $n$ hnútum tölusettum $1,2,\dots,n$. Netið er kallað _keppnisnet_ ef nákvæmlega einn leggur milli allra para hnúta í einhverja átt. Það er, fyrir hvert par mismunandi hnúta $u$ og $v$, það er annað hvort leggur frá $u$ til $v$ eða frá $v$ til $u$.

Hamilton-rás er runa $c_1, c_2, \dots, c_n$ sem fer eftir leggjum í gegnum alla hnúta og endar aftur í byrjun. Fyrir öll $1 \le i \le n-1$, þarf að vera leggur frá $c_i$ til $c_{i+1}$. Auk þess, þarf að vera leggur frá $c_n$ til $c_1$.
 
Þú getur frjálslega búið til keppnisnet úr $n$ hnútum. Tölusetningu hnútanna er síðan stokkað upp. Með því að gera fyrirspurnir um áttir leggjanna í stokkaða netinu, getur þú fundið Hamilton-rás?

# Gagnvirkni

Þetta er gagnvirkt verkefni. Byrjaðu að því að lesa tvær heiltölur $n$ og $t$: fjöldi hnúta og fjöldi prófunartilvika.

Næst, prentaðu út $n$ línur sem útskyra keppnisnetið. Á $u$-tu línu prentið út $n$ stafi "`0`" eða "`1`". Talan "`1`" á stað $v$ að það er leggur frá $u$ til $v$. Það á ekki að vera leggur frá $u$ til sjálfs sín.

Eftir það eru $t$ prófunartilvik. Hvert prófunartilvik notar sama net sem þú hefur gefið en tölusetningin hnúta er stokkuð upp og haldið leyndu af yfirferðarforritinu. 
Þú getur gert nokkrar fyrirspurnir. Eftir það ættir þú að prenta út Hamilton-rás.

Til að gera fyrirspurn, prentaðu út "`?` $u$ $v$", þar sem $1 \le u,v \le n$ eru mismunandi hnútar í stokkaða netinu. Yfirferðarforritið svarar með annað hvort "`>`", ef það er leggur frá $u$ til $v$, eða "`<`" ef það er leggur frá $v$ til $u$.

Þegar þú hefur fundið Hamilton-rás, prentaðu út "`!`" og síðan $n$ heiltölur $c_1, c_2, \dots, c_n$. Takið eftir að tölurnar $c_i$ ættu að fylgja stokkuðu tölusetninguni. Næsta prófunartilvik byrjar strax eftir það.

Hægt er að hlaða niður prófunarforriti [hérna](files/hamilton-test.py). Í upphafi forritsins eru leiðbeiningar um hvernig á að nota það.

# Takmarkanir

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

# Gagnvirkni dæmi

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

_Explanation:_ Hnútarnir eru tilviljunarkennt stokkaðir í upprunalega röð í fyrsta prófunartilvikinu og því er $1,2,3,4,5$ Hamilton-rás.

Í öðru prófunartilvikinu, hnútar númer $1,2,3,4,5$ eru stokkaðir í $2,4,1,5,3$, í þessari röð. Runan $1,5,4,3,2$ er sannarlega Hamilton-rás þar sem $3,4,2,5,1$ var það í upprunalega netinu.

Í myndinni hér fyrir neðan, er upprunalega netið sýnt vinstra megin og stokkaða netið frá öðru prófunartilvikinu er sýnt hægra megin. Hamilton-rásirnar tvær eru merktar með rauðu.

![Mynd af dæminu](files/example.svg "=420x")

# Stigagjöf

Það er aðeins eitt prófunarinntak í hverjum hópi, með $t = 200$ prófunartilvik. Í hverju prófunartilviki er tölusetning netsins stokkuð jafnt af handahófi. Ef gerðar eru fleiri en $10^4$  fyrirspurnir í einu prófunartilviki leiðir til niðurstöðunnar WRONG ANSWER.

Látum $Q$ vera meðalfjöldi fyrirspurna sem forritið þitt gerir meðal allra prófunartilvika sem tilheyra hópi. Þú færð stig fyrir þann hóp ef $Q$ er ekki stærra en tilgreint mörk.

| Hópur | Takmarkanir | Stig |
| :-----: | ----------- | :-------: |
| 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 |

Í hópi 4 færðu stig samkvæmt eftirfarandi formúlu:

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

Til dæmis, ef meðalfjöldi fyrirspurna sem forritið þitt gerir er $Q=1500$, þú færð 1 stig fyrir hópinn. Ef $Q = 1000$ færðu 26 stig, og ef $Q = 750$ færðu 76 stig.
