Problem B
Skatīšanās sacensības

Skatīšanās sacensības ir klasiska izturības cīņa, kur divi cilvēki skatās viens otra acīs, uzturot mierīgu sejas izteiksmi. Mērķis ir saglabāt acu kontaktu ilgāk par pretinieku. Sacensības beidzas, kad viens dalībnieks zaudē koncentrēšanos, piemēram, novēršot skatienu, smaidot, runājot vai smejoties.

Kā nacionālajam skatīšanās sacensību trenerim, jums ir jānosaka katra komandas dalībnieka izturība gaidāmajā pasaules finālā, kur komanda sastāv no $n$ dalībniekiem. $i$-tais sportists var uzturēt acu kontaktu tieši $a_ i$ sekundes, bet šīs vērtības jums sākumā nav zināmas. Piemēram, jūsu komanda varētu sastāvēt no $n=3$ dalībniekiem:

Kad $i$-tais un $j$-tais dalībnieks sacenšas, konfrontācija ilgst tieši $\min (a_ i, a_ j)$ sekundes, tajā brīdī vājākais dalībnieks zaudē koncentrēšanos un pēc mirkļa abi dalībnieki sāk smaidīt un smieties. Piemēram, ja Anna sacenšas ar Esteri, sacensības ilgst $431$ sekundes. Svarīgi ir atzīmēt, ka vērotājam no malas faktisko uzvarētāju konfrontācijā (šajā gadījumā Estere) ir neiespējami noteikt, izmērāms ir tikai konfrontācijas ilgums.

Jūsu mērķis ir noteikt $a_1,\ldots , a_ n$ vērtības, izmantojot pēc iespējas mazāk skatīšanās sacensību. Skaidrs, ka spēcīgākā sportista spēku nekad nevar noteikt, tāpēc jums ir atļauts novērtēt par zemu vienu no $a_ i$ vērtībām.

Komunikācija

Šis ir interaktīvs uzdevums. Komunikācija sākas ar vienas rindas lasīšanu, kas satur veselu skaitli $n$. Tad jūs varat vaicāt pieprasījumus, kas ir formātā "? $i$ $j$", kur $1\leq i\leq n$ un $1\leq j\leq n$ un $i\neq j$. Atbilde uz jūsu pieprasījumu būs viens vesels skaitlis: $\min (a_ i, a_ j)$ vērtība. Komunikācija beidzas ar vienas rindas izdrukāšanu, kas sastāv no !, aiz kura seko $n$ noteiktie veselie skaitļi $b_1$, $\ldots $, $b_ n$, kas atdalīti ar atstarpi. Šai ir jābūt pēdejai izvada rindai.

Jūsu risinājums ir pareizs, ja $b_ i=a_ i$ katram dalībniekam $i$, izņemot vienu, kuram sagaidāmo iztūrību drīkst novērtēt par zemu. Precīzāk, tiek sagaidīts, ka $b_ i\leq a_ i$ visiem $1\leq i\leq n$ un atļaujam, ka $b_ k \neq a_ k$ ne vairāk kā vienai $k$ vērtībai.

Testēšānas sistēmas komunikācijas programma ir neadaptīva, kas nozīmē, ka $a_1,\ldots , a_ n$ tiek fiksētas pirms komunikācijas sākuma.

Ierobežojumi un vērtēšana

Dalībnieku skaits $n$ atbilst ierobežojumam: $2\leq n\leq 1500$. Katra dalībnieka izturība $a_ i$ atbilst ierobežojumiem: $1\leq a_ i\leq 86\, 400$, visas vērtības ir atšķirīgas. Jūs varat veikt ne vairāk kā $3000$ vaicājumus; beidzamā izvada rinda, t.i., rinda, kas sākas ar !, netiek skaitīta kā vaicājums.

Jūsu risinājums tiks pārbaudīts uz vairākām testu grupām, kur katra grupa ir vērta noteiktu punktu skaitu. Katra testu grupa satur vairākus testus. Lai saņemtu punktus par testu grupu, ir jāatrisina visi testi testu grupā. Jūsu gala rezultāts būs lielākais punktu skaits, kas iegūts ar vienu risinājuma iesniegumu.

$3.$ grupai jūsu rezultāts ir vismazākais punktu skaits starp visiem testiem testu grupā. Katram testam punktu skaits ir atkarīgs no pieprasījumu skaita, ko jūs veiksiet; mazāk pieprasījumu ir labāk. Pieņemsim, ka jūs izmantojat $q$ pieprasījumus. Ja $q \le n+25$, tad jūs saņemsiet visus $80$ punktus. Ja $q > 3000$, tad jūs nesaņemsiet punktus. Citādi jūs saņemsiet $118.2 - 12 \cdot \ln (q - n)$ punktus, kas noapaļoti līdz tuvākajam veselam skaitlim. Piemēram, ja $n = 1500$ un $q = 3000$, tad jūs saņemsiet $30$ punktus.

Parauga komunikācijas skaidrojums

$1.$ piemēra komunikācija demonstrē iepriekš aprakstīto piemēru. Pievērsiet uzmanību, ka Annas un Tonija izturības ir pareizi noteiktas. (Esteres spējas nevar pareizi noteikt.)

3

? 1 2

431

? 1 3

121

? 3 2

121

! 431 431 121