Problem B
Tuijotuskilpailu

Tuijotuskilpailu on klassinen häiriintymättömyyden taistelu, jossa kaksi ihmistä tuijottavat toisiaan silmiin ylläpitäen samalla varman neutraalia ilmettä. Tavoitteena on säilyttää katsekontakti vastustajaa pidempään. Kilpailu loppuu, kun toinen osallistujista ei saa enää pidettyä pokkaansa, vaan esimerkiksi katsoo pois, hymyilee, puhuu tai nauraa.

Kansallisen tuijotuskilpailun valmentajana sinun täytyy selvittää jokaisen joukkueesi $n$:n jäsenen häiriintymättömyys tulevaa maailmanmestaruuskilpailua varten. Kilpailijoista $i$:s pystyy ylläpitämään katsekontaktia tasan $a_ i$ sekuntia, mutta et tiedä näitä arvoja alussa. Esimerkiksi, sinulla voisi olla joukkue, jossa on $n=3$ jäsentä:

Kun kisajaat $i$ ja $j$ kilpailevat, heidän yhteenottonsa kestää tarkalleen $\min (a_ i, a_ j)$ sekuntia, minkä jälkeen heikomman kisaajan pokka pettää ja molemmat alkavat hymyillä ja kikattaa sekunnin murto-osassa. Jos esimerkiksi Anna kilpailee Estheriä vastaan, kisa kestää $431$ sekuntia. Huomaa, että ulkopuolisen tarkastelijan on mahdotonta päätellä kisan voittajaa (tässä tapauksessa Esther), vaan ainoastaan kisan kesto on mitattavissa.

Tehtäväsi on arvioida lukuja $a_1,\ldots , a_ n$ käyttäen mahdollisimman pientä määrää tuijotuskilpailuja. Parhaimman kisaajan häiriintymättömyyttä on selvästi mahdotonta määrittää, joten saat aliarvioida yhden luvuista $a_ i$.

Interaktio

Tämä on interaktiivinen tehtävä. Interaktio alkaa sillä, että luet yhden rivin, joka sisältää kokonaisluvun $n$. Voit tehdä kyselyitä muotoa “? $i$ $j$”, missä $1\leq i\leq n$, $1\leq j\leq n$ ja $i\neq j$. Vastaus kyselyyn on yksi kokonaisluku: kesto $\min (a_ i, a_ j)$. Interaktio loppuu, kun tulostat yhden rivin, joka koostuu merkistä ! ja $n$ arviosta välilyönneillä erotettuina kokonaislukuina $b_1$, $\ldots $, $b_ n$. Tämän täytyy olla tulosteesi viimeinen rivi.

Ratkaisusi katsotaan oikeaksi, jos $b_ i=a_ i$ jokaiselle kisaajalle $i$, paitsi yhdelle, jonka häiriintymättömyyden saat aliarvioida. Tarkalleen ottaen vaadimme, että $b_ i\leq a_ i$ kaikille $1\leq i\leq n$ ja sallimme $b_ k \neq a_ k$ korkeintaan yhdelle $k$:lle.

Tehtävän interaktori ei ole adaptiivinen, eli luvut $a_1,\ldots , a_ n$ ovat päätetty ennen interaktion alkamista.

Rajoitukset ja pisteytys

Kisaajien määrälle $n$ pätee $2\leq n\leq 1500$. Kisaajien häiriintymättömyyksille $a_ i$ pätee $1\leq a_ i\leq 86\, 400$, ja ne ovat kaikki erisuuria keskenään. Voit käyttää enintään $3000$ kyselyä; viimeistä tulosteriviäsi, eli merkillä ! alkavaa riviä, ei lasketa kyselyksi.

Ratkaisu testataan testiryhmillä, joista kullakin on oma pistemäärä. Jokainen testiryhmä sisältää joukon testitapauksia. Ryhmän pisteet saa vain, jos ratkaisee kaikki sen testitapaukset. Tehtävän lopullinen pistemäärä on suurin yksittäisen lähetyksen pistemäärä.

Ryhmässä $3$ pistemääräsi on kaikkien ryhmän testien pienin pistemäärä. Yhden testitapauksen pistemäärä riippuu käyttämiesi kyselyiden määrästä; mitä vähemmän kyselyita, sen parempi: Oletetaan, että teet $q$ kyselyä. Jos $q \le n+25$, niin saat täydet $80$ pistettä. Jos $q > 3000$, niin saat nolla pistettä. Muussa tapauksessa saat $118.2 - 12 \cdot \ln (q - n)$ pistettä, pyöristettynä lähimpään kokonaislukuun. Jos esimerkiksi $n = 1500$ ja $q = 3000$, niin saat $30$ pistettä.

Selitys esimerkkitapauksille

Esimerkki $1$ näyttää mahdollisen interaktion ylläolevalle esimerkille. Huomaa, että Annan ja Tonyn häiriintymättömyydet on määritetty oikein. (Estherin häiriintymättömyyttä ei voida määrittää.)

3

? 1 2

431

? 1 3

121

? 3 2

121

! 431 431 121