Tämä on viestintätehtävä (communication problem).
Kaksi ohjelmaa, Alice ja Bob, pelaavat seuraavaa yhteistyöpeliä.
Annettuna ovat kokonaisluvut $A$ ja $B$, joille $0 \le A, B < 2^{64}$. Aluksi vain Alice tietää luvun $A$ ja vain Bob tietää luvun $B$. Olkoon $C := \min(A, B)$. Tavoitteena on, että sekä Alice että Bob pystyvät tulostamaan luvun $C$.
Vaihtaakseen tietoja Alice ja Bob voivat kutsua seuraavia funktioita:
send(x): Lähetä 1-bittinen arvo $x$ toiselle ohjelmalle. Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiotareceive().receive(): Vastaanota 1-bittinen arvo toiselta ohjelmalta ja palauta se. Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiotasend().
Alicen ja Bobin tekemien send()-kutsujen yhteismäärä saa olla enintään $76$. Sama pätee funktioon receive().
Kun viestintä on päättynyt, kummankin ohjelman on kutsuttava seuraavaa funktiota täsmälleen kerran:
answer(x): Ilmoita, että luvun $C$ arvo on $x$. Välittömästi tämän funktion kutsumisen jälkeen ohjelman on päätyttävä.
Peli onnistuu, jos sekä Alice että Bob vastaavat $C$ oikein.
Kirjoita kaksi ohjelmaa, Alice ja Bob, jotka onnistuvat pelissä aina.
Vuorovaikutusprotokolla
Tämä on vuorovaikutteinen viestintätehtävä (ohjelmasi ja tuomariohjelma kommunikoivat standardisyötteen ja -tulosteen kautta). Alicena toimiva ohjelmasi ja Bobina toimiva ohjelmasi pelaavat peliä tuomariohjelman välityksellä.
Ohjelman käynnistys
Ohjelmasi saa ensin syötteen seuraavassa muodossa:
Player X
Tässä Player on merkkijono Alice tai Bob, ja $X$ on kokonaisluku, jolle $0 \le X < 2^{64}$.
- Jos
PlayeronAlice, niin $A = X$. Tästä eteenpäin ohjelmasi on toimittava Alicena. - Jos
PlayeronBob, niin $B = X$. Tästä eteenpäin ohjelmasi on toimittava Bobina.
Kutsu sen jälkeen funktioita send, receive ja lopuksi answer alla kuvatulla tavalla.
send
Kutsuaksesi send(x), tulosta:
send x
Tässä $x$:n on oltava $0$ tai $1$.
Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiota receive(). Saat tuloksen Wrong Answer, jos jokin seuraavista tapahtuu:
- toinen ohjelma päättyy odottaessasi,
- toinen ohjelma kutsuu myös funktiota
send()odottaessasi, - Alicen ja Bobin tekemien
send()-kutsujen yhteismäärä ylittää $76$.
receive
Kutsuaksesi receive(), tulosta:
receive
Lue sitten vastaanotettu bitti $x$ standardisyötteestä:
x
Tämä kutsu ei palaa ennen kuin toinen ohjelma kutsuu funktiota send(). Saat tuloksen Wrong Answer, jos jokin seuraavista tapahtuu:
- toinen ohjelma päättyy odottaessasi,
- toinen ohjelma kutsuu myös funktiota
receive()odottaessasi, - Alicen ja Bobin tekemien
receive()-kutsujen yhteismäärä ylittää $76$.
Jos saat vuorovaikutuksen aikana tuloksen Wrong Answer, syötteenä annetaan $-1$. Jos luet arvon $-1$, lopeta ohjelmasi välittömästi, tai muuten saatat saada tuloksen Time Limit Exceeded.
answer
Kutsuaksesi answer(x), tulosta:
answer x
Tässä $x$:n on oltava yhtä suuri kuin $\min(A, B)$. Lopeta ohjelmasi välittömästi tämän funktion kutsumisen jälkeen.
Huomautus
- Jokaisen tulostuksen jälkeen ohjelmasi on tyhjennettävä standarditulosteen puskuri (flush); muuten saatat saada tuloksen Time Limit Exceeded.
- Tuomariohjelma, Alicena toimiva ohjelmasi ja Bobina toimiva ohjelmasi suoritetaan samanaikaisesti. Aika- ja muistirajat mitataan näiden kaikkien kolmen summana, joten jätä riittävästi marginaalia sekä ajalle että muistinkäytölle.
- Tuomariohjelma kuluttaa enintään noin $50$ ms ja $5$ MiB.
- Käsittelet kokonaislukuja välillä $0$ – $2^{64} - 1$. Varo ylivuotoa (overflow).
Esimerkit
Esimerkkisyöte 1
Alice 31 1
Esimerkkituloste 1
send 0 receive send 1 answer 25
Esimerkkisyöte 2
Bob 25 0 1
Esimerkkituloste 2
receive send 1 receive answer 25