Problem B
Stirrekonkurrence

En stirrekonkurrence er en klassisk konfrontation af to personers evne til at stirre den anden i øjnene under opretholdelsen af et ansigtsudtryk præget af ophøjet og behersket sindsligevægt. Man vinder ved at holde øjenkontakten længere end modstanderen. Konkurrencen slutter, når den ene deltager taber fatningen, typisk ved at kigge væk, smile, tale eller fnise.

Som træner for stirrelandsholdet skal du til verdensmesterskaberne bestemme uforstyrreligheden for hvert af landsholdets $n$ medlemmer. Den $i$’te atlet kan opretholde øjenkontakt i præcis $a_ i$ sekunder, men disse værdier er ukendte for dig i begyndelsen. For eksempel kan dit hold bestå af $n=3$ medlemmer:

Når atlet $i$ konkurrerer mod atlet $j$, varer konfrontationen præcis $\min (a_ i, a_ j)$ sekunder, hvorpå den svagere deltager taber fatningen, og begge deltagerne umiddelbart begynder at smile eller grine. Hvis Anna for eksempel konkurrerer mod Esther, varer konkurrencen i $431$ sekunder. Det er vigtigt at understrege, at det for en udenforstående observatør er umuligt at bestemme den faktiske vinder af konfrontationen (i dette tilfælde, Esther). Kun varigheden af konkurrencen er målbar.

Du skal estimere værdierne $a_1,\ldots , a_ n$ med så få stirrekonkurrencer som muligt. Det er klart, at den stærkeste atlets styrke aldrig vil kunne blive bestemt, så du har lov til at undervurdere én af $a_ i$’erne.

Interaktion

Dette er et interaktivt problem. Interaktionen begynder med, at du læser en enkelt linje, der indeholder tallet $n$. Herefter kan du stille spørgsmål på formen “? $i$ $j$”, hvor $1\leq i\leq n$, $1\leq j\leq n$ og $i\neq j$. Svaret på dit spørgsmål er et enkelt tal: værdien $\min (a_ i, a_ j)$. Interaktionen slutter, når du udskriver en enkelt linje bestående af ! efterfulgt af dine estimater $b_1$, $\ldots $, $b_ n$, adskilte af mellemrum. Derefter må du ikke skrive mere.

Din indsendelse er korrekt, hvis $b_ i=a_ i$ for hver deltager $i$ undtagen én, som du måske undervurderer. Mere præcist skal der gælde $b_ i\leq a_ i$ for alle $1\leq i\leq n$, og vi tillader $b_ k \neq a_ k$ for højst ét $k$.

Opgaven er ikke-adaptiv, hvilket betyder, at $a_1,\ldots , a_ n$ er bestemt før interaktionen begynder.

Begrænsninger og pointgivning

Antallet $n$ af atleter opfylder $2\leq n\leq 1500$. Uforstyrreligheden $a_ i$ for hver atlet opfylder $1\leq a_ i\leq 86\, 400$, de er alle forskellige. Du må stille højst $3000$ spørgsmål; din sidst udskrevne linje, dvs. linjen, der starter med !, tælles ikke som spørgsmål.

Din løsning vil blive testet på en række testgrupper, hver med en vist antal point. Hver testgruppe indeholder en række testfald. For at opnå point for en testgruppe skal du løse alle testfald i testgruppen. Din endelige score vil være den højeste score for en enkelt indsendelse.

For gruppe $3$ er din score den minimale score blandt alle testfald i gruppen. Scoren for hvert testfald afhænger af antallet af forespørgsler, du bruger; færre forespørgsler er bedre. Antag, at du bruger $q$ forespørgsler. Hvis $q \le n+25$, får du de fulde $80$ point. Hvis $q > 3000$, får du ingen point. Ellers får du $118,2 - 12 \cdot \ln (q - n)$ point, afrundet til nærmeste heltal. For $n = 1500$ og $q = 3000$ får du for eksempel $30$ point.

Forklaring af eksempelinteraktionen

Eksempelinteraktion $1$ viser en mulig interaktion med brug af ovenstående eksempel. Bemærk, at Annas og Tonys styrker er korrekt bestemte. (Esthers kan aldrig bestemmes.)

3

? 1 2

431

? 1 3

121

? 3 2

121

! 431 431 121