Þetta er samskiptaverkefni.
Tvö forrit, Alice og Bob, spila eftirfarandi samvinnuleik.
Gefnar eru heiltölurnar $A$ og $B$ með $0 \le A, B < 2^{64}$. Í upphafi veit aðeins Alice gildið á $A$ og aðeins Bob veit gildið á $B$. Látum $C := \min(A, B)$. Markmiðið er að bæði Alice og Bob geti skrifað út $C$.
Til að skiptast á upplýsingum mega Alice og Bob kalla á eftirfarandi föll:
send(x): Senda 1-bita gildi $x$ til hins forritsins. Þetta kall skilar sér ekki fyrr en hitt forritið kallar áreceive().receive(): Taka á móti 1-bita gildi frá hinu forritinu og skila því. Þetta kall skilar sér ekki fyrr en hitt forritið kallar ásend().
Heildarfjöldi kalla á send() sem Alice og Bob gera samanlagt má ekki fara yfir $76$. Hið sama gildir um receive().
Eftir að samskiptum lýkur verður hvort forrit að kalla á eftirfarandi fall nákvæmlega einu sinni:
answer(x): Lýsa því yfir að gildið á $C$ sé $x$. Strax eftir að kallað er á þetta fall verður forritið að hætta keyrslu.
Leikurinn tekst ef bæði Alice og Bob svara $C$ rétt.
Skrifaðu tvö forrit, Alice og Bob, sem ná alltaf árangri í leiknum.
Samskiptareglur
Þetta er gagnvirkt samskiptaverkefni (forritin þín og dómarinn eiga samskipti í gegnum staðlað inntak/úttak). Forritið þitt í hlutverki Alice og forritið þitt í hlutverki Bob munu spila leikinn í gegnum dómarann.
Ræsing forrits
Forritið þitt fær fyrst inntak á eftirfarandi sniði:
Player X
Hér er Player strengurinn Alice eða Bob, og $X$ er heiltala með $0 \le X < 2^{64}$.
- Ef
PlayererAlice, þá er $A = X$. Frá þessum tímapunkti verður forritið þitt að hegða sér sem Alice. - Ef
PlayererBob, þá er $B = X$. Frá þessum tímapunkti verður forritið þitt að hegða sér sem Bob.
Eftir það skaltu kalla á send, receive og að lokum answer eins og lýst er hér að neðan.
send
Til að kalla á send(x) skaltu prenta:
send x
Hér verður $x$ að vera $0$ eða $1$.
Þetta kall skilar sér ekki fyrr en hitt forritið kallar á receive(). Þú færð Wrong Answer ef eitthvað af eftirfarandi gerist:
- hitt forritið hættir keyrslu á meðan þú bíður,
- hitt forritið kallar líka á
send()á meðan þú bíður, - heildarfjöldi kalla á
send()hjá Alice og Bob fer yfir $76$.
receive
Til að kalla á receive() skaltu prenta:
receive
Lestu síðan móttekna bitann $x$ úr stöðluðu inntaki:
x
Þetta kall skilar sér ekki fyrr en hitt forritið kallar á send(). Þú færð Wrong Answer ef eitthvað af eftirfarandi gerist:
- hitt forritið hættir keyrslu á meðan þú bíður,
- hitt forritið kallar líka á
receive()á meðan þú bíður, - heildarfjöldi kalla á
receive()hjá Alice og Bob fer yfir $76$.
Ef þú færð Wrong Answer í samskiptunum verður inntakið sem gefið er $-1$. Ef þú lest $-1$ skaltu stöðva forritið þitt samstundis, annars gætirðu fengið Time Limit Exceeded.
answer
Til að kalla á answer(x) skaltu prenta:
answer x
Hér verður $x$ að vera jafnt $\min(A, B)$. Eftir að kallað er á þetta fall skaltu stöðva forritið þitt samstundis.
Athugasemd
- Eftir hvert úttak verður forritið þitt að tæma staðlað úttak (flush); annars gætirðu fengið Time Limit Exceeded.
- Dómaraforritið, forritið þitt sem Alice og forritið þitt sem Bob keyra samtímis. Tíma- og minnistakmörk eru mæld sem summa þeirra allra, svo skildu eftir nægilegt svigrúm fyrir bæði tíma og minni.
- Dómaraforritið notar allt að um $50$ ms og $5$ MiB.
- Þú munt vinna með heiltölur á bilinu $0$ til $2^{64} - 1$. Gættu að yfirflæði (overflow).
Dæmi
Dæmi um inntak 1
Alice 31 1
Dæmi um úttak 1
send 0 receive send 1 answer 25
Dæmi um inntak 2
Bob 25 0 1
Dæmi um úttak 2
receive send 1 receive answer 25