Hide

Problem B
Tuijotuskilpailu

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

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 ai sekuntia, mutta et tiedä näitä arvoja alussa. Esimerkiksi, sinulla voisi olla joukkue, jossa on n=3 jäsentä:

i

Nimi

ai

1

Anna

431

2

Esther

623

3

Tony

121

Kun kisajaat i ja j kilpailevat, heidän yhteenottonsa kestää tarkalleen min(ai,aj) 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 a1,,an 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 ai.

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ä 1in, 1jn ja ij. Vastaus kyselyyn on yksi kokonaisluku: kesto min(ai,aj). Interaktio loppuu, kun tulostat yhden rivin, joka koostuu merkistä ! ja n arviosta välilyönneillä erotettuina kokonaislukuina b1, , bn. Tämän täytyy olla tulosteesi viimeinen rivi.

Ratkaisusi katsotaan oikeaksi, jos bi=ai jokaiselle kisaajalle i, paitsi yhdelle, jonka häiriintymättömyyden saat aliarvioida. Tarkalleen ottaen vaadimme, että biai kaikille 1in ja sallimme bkak korkeintaan yhdelle k:lle.

Tehtävän interaktori ei ole adaptiivinen, eli luvut a1,,an ovat päätetty ennen interaktion alkamista.

Rajoitukset ja pisteytys

Kisaajien määrälle n pätee 2n1500. Kisaajien häiriintymättömyyksille ai pätee 1ai86400, 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 qn+25, niin saat täydet 80 pistettä. Jos q>3000, niin saat nolla pistettä. Muussa tapauksessa saat 118.212ln(qn) pistettä, pyöristettynä lähimpään kokonaislukuun. Jos esimerkiksi n=1500 ja q=3000, niin saat 30 pistettä.

Ryhmä

Pisteet

Rajoitukset

1

9

n50

2

11

n1000

3

080

1000<n1500

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

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

Please log in to submit a solution to this problem

Log in