Hide

Problem B
Stirrekonkurrence

Languages da de en fi lt lv pl uk
/problems/boi23.staringcontest/file/statement/da/img-0001.png

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 ai sekunder, men disse værdier er ukendte for dig i begyndelsen. For eksempel kan dit hold bestå af n=3 medlemmer:

i

Navn

ai

1

Anna

431

2

Esther

623

3

Tony

121

Når atlet i konkurrerer mod atlet j, varer konfrontationen præcis min(ai,aj) 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 a1,,an 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 ai’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 1in, 1jn og ij. Svaret på dit spørgsmål er et enkelt tal: værdien min(ai,aj). Interaktionen slutter, når du udskriver en enkelt linje bestående af ! efterfulgt af dine estimater b1, , bn, adskilte af mellemrum. Derefter må du ikke skrive mere.

Din indsendelse er korrekt, hvis bi=ai for hver deltager i undtagen én, som du måske undervurderer. Mere præcist skal der gælde biai for alle 1in, og vi tillader bkak for højst ét k.

Opgaven er ikke-adaptiv, hvilket betyder, at a1,,an er bestemt før interaktionen begynder.

Begrænsninger og pointgivning

Antallet n af atleter opfylder 2n1500. Uforstyrreligheden ai for hver atlet opfylder 1ai86400, 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 qn+25, får du de fulde 80 point. Hvis q>3000, får du ingen point. Ellers får du 118,212ln(qn) point, afrundet til nærmeste heltal. For n=1500 og q=3000 får du for eksempel 30 point.

Gruppe

Point

Begrænsninger

1

9

n50

2

11

n1000

3

080

1000<n1500

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.)

Read Sample Interaction 1 Write
3
? 1 2
431
? 1 3
121
? 3 2
121
! 431 431 121
Hide