Problem B
Spoksojimo varžybos

Spoksojimo varžybos yra klasikinė šaltakraujiškumo dvikova, kurioje du varžovai spokso vienas į kitą stengdamiesi išlaikyti užtikrintą ramybę veide. Varžybų tikslas – išlaikyti akių kontaktą ilgiau nei priešininkas. Dvikova baigiama, kai vienas iš dalyvių sudrumsčia ramybės būseną. Įprastai tai nutinka dalyviui pažiūrėjus į šalį, nusišypsojus, prašnekus ar sukikenus.

Esate nacionalinių spoksojimo varžybų treneris, ir artėjančiam pasaulinių varžybų finalui norite sužinoti kiekvieno iš jūsų $n$ komandos narių šaltakraujiškumo lygį. $i$-tasis sportininkas gali išlaikyti akių kontaktą lygiai $a_ i$ sekundžių, bet pradžioje šių reikšmių nežinote. Pavyzdžiui, jūsų komandoje $n=3$ nariai:

Kai varžosi $i$-tasis ir $j$-tasis sportininkai, jų akistata trunka lygiai $\min (a_ i, a_ j)$ sekundžių, po kurių silpnesnis varžovas sudrumsčia ramybę ir per sekundės dalį abu dalyviai ima šypsotis ir kikenti. Pavyzdžiui, jei Anna varžytųsi su Esther, ši dvikova truktų $431$ sekundę. Svarbu tai, kad išorinis stebėtojas negali nustatyti akistatos laimėtojo (šiuo atveju, Esther). Stebėtojas gali išmatuoti tik trukmę.

Išsiaiškinkite $a_1,\ldots , a_ n$ reikšmes surengdami kuo mažiau spoksojimo varžybų. Aišku, stipriausiojo sportininko stiprumo neįmanoma nustatyti, tad galite nuvertinti (t. y. nurodyti mažesnę) vieną iš $a_ i$ reikšmių.

Sąveika

Užduotis yra interaktyvi. Pradiniu momentu pateikiamas sveikasis skaičius $n$ (viena eilutė). Tuomet galite išvesti užklausas formatu ,,? $i$ $j$“, kur $1\leq i\leq n$ ir $1\leq j\leq n$ bei $i\neq j$. Atsakymas į užklausą yra vienas sveikasis skaičius: reikšmė $\min (a_ i, a_ j)$. Sąveika baigiama kai išvedate vieną eilutę, kurioje yra simbolis ! ir $n$ spėjimų: tarpais atskirtų sveikųjų skaičių $b_1$, $\ldots $, $b_ n$. Tai turi buti paskutinioji jūsų programos išvesties eilutė.

Sprendimas laikomas teisingu, jeigu $b_ i=a_ i$ kiekvienam dalyviui $i$, išskyrus vienam, kurį galite nuvertinti. Tai yra, reikalaujama, kad visiems $1\leq i\leq n$ galiotų $b_ i\leq a_ i$ ir daugiausiai vienam $k$ galiotų $b_ k \neq a_ k$.

Sąveikos programa nėra adaptyvi. Tai reiškia, kad reikšmės $a_1,\ldots , a_ n$ yra nustatomos prieš prasidedant sąveikai.

Ribojimai ir vertinimas

Sportininkų skaičiui $n$ galioja $2\leq n\leq 1500$. Kiekvieno sportininko šaltakraujiškumo lygiui $a_ i$ galioja $1\leq a_ i\leq 86\, 400$, visos šios reikšmės skirtingos. Galite atlikti daugiausiai $3000$ užklausų; paskutinė programos išvesties eilutė, t.y., eilutė, prasidedanti simboliu !, nėra laikoma užklausa.

Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kurių kiekviena verta tam tikro skaičiaus taškų. Kiekviena testų grupė sudaryta iš įvairių testų. Testų grupės taškai skiriami tik išsprendus visus tos grupės testus. Galutinis rezultatas lygus daugiausiai surinkusio sprendimo taškų skaičiui.

$3$-iosios testų grupės rezultatas lygus mažiausiam kurio nors šios grupės testo taškų skaičiui. Kiekvieno testo taškai priklauso nuo to, kiek užklausų atliekate; kuo mažiau užklausų, tuo geriau. Tarkime, kad atliekate $q$ užklausų. Jei $q \le n+25$, tai gaunate visus $80$ taškų. Jei $q > 3000$, negaunate taškų. Kitu atveju, gaunate $118.2 - 12 \cdot \ln (q - n)$ taškų, suapvalinus iki artimiausio sveikojo skaičiaus. Pavyzdžiui, jeigu $n = 1500$ ir $q = 3000$, gautumėte $30$ taškų.

Sąveikos pavyzdžio paaiškinimas

Žemiau (Sample Interaction $1$) parodyta galima sąveika naudojant aukščiau aprašytą pavyzdį. Pastebėkite, kad Annos ir Tony stiprumai yra nustatyti teisingai, o Esther stiprumo neįmanoma nustatyti.

3

? 1 2

431

? 1 3

121

? 3 2

121

! 431 431 121