Dette er en kommunikasjonsoppgave.
To programmer, Alice og Bob, spiller følgende samarbeidsspill.
Du får gitt heltallene $A$ og $B$ med $0 \le A, B < 2^{64}$. Til å begynne med er det bare Alice som kjenner $A$, og bare Bob som kjenner $B$. La $C := \min(A, B)$. Målet er at både Alice og Bob skal kunne skrive ut $C$.
For å utveksle informasjon kan Alice og Bob kalle følgende funksjoner:
send(x): Send en 1-bits verdi $x$ til det andre programmet. Dette kallet returnerer ikke før det andre programmet kallerreceive().receive(): Motta en 1-bits verdi fra det andre programmet og returner den. Dette kallet returnerer ikke før det andre programmet kallersend().
Det totale antallet kall til send() gjort av Alice og Bob til sammen må ikke overstige $76$. Det samme gjelder for receive().
Etter at kommunikasjonen er ferdig, må hvert program kalle følgende funksjon nøyaktig én gang:
answer(x): Erklær at verdien av $C$ er $x$. Umiddelbart etter at denne funksjonen er kalt, må programmet avslutte.
Spillet er vellykket hvis både Alice og Bob svarer $C$ riktig.
Skriv to programmer, Alice og Bob, som alltid lykkes i spillet.
Interaksjonsprotokoll
Dette er en interaktiv kommunikasjonsoppgave (programmene dine og dommeren kommuniserer via standard inndata/utdata). Programmet ditt som opptrer som Alice og programmet ditt som opptrer som Bob vil spille spillet gjennom dommeren.
Programstart
Programmet ditt mottar først inndata på følgende format:
Player X
Her er Player strengen Alice eller Bob, og $X$ er et heltall med $0 \le X < 2^{64}$.
- Hvis
PlayererAlice, så er $A = X$. Fra dette tidspunktet må programmet ditt oppføre seg som Alice. - Hvis
PlayererBob, så er $B = X$. Fra dette tidspunktet må programmet ditt oppføre seg som Bob.
Deretter kaller du send, receive og til slutt answer som beskrevet nedenfor.
send
For å kalle send(x), skriv ut:
send x
Her må $x$ være $0$ eller $1$.
Dette kallet returnerer ikke før det andre programmet kaller receive(). Du vil bli dømt som Wrong Answer hvis noe av det følgende skjer:
- det andre programmet avslutter mens du venter,
- det andre programmet kaller også
send()mens du venter, - det totale antallet kall til
send()gjort av Alice og Bob overstiger $76$.
receive
For å kalle receive(), skriv ut:
receive
Les deretter den mottatte biten $x$ fra standard inndata:
x
Dette kallet returnerer ikke før det andre programmet kaller send(). Du vil bli dømt som Wrong Answer hvis noe av det følgende skjer:
- det andre programmet avslutter mens du venter,
- det andre programmet kaller også
receive()mens du venter, - det totale antallet kall til
receive()gjort av Alice og Bob overstiger $76$.
Hvis du blir dømt som Wrong Answer under interaksjonen, vil inndataene som gis være $-1$. Hvis du leser $-1$, må du avslutte programmet umiddelbart, ellers kan du få Time Limit Exceeded.
answer
For å kalle answer(x), skriv ut:
answer x
Her må $x$ være lik $\min(A, B)$. Etter å ha kalt denne funksjonen, avslutt programmet umiddelbart.
Merk
- Etter hver utskrift må programmet ditt tømme standard utdata (flush); ellers kan du få Time Limit Exceeded.
- Dommerprogrammet, programmet ditt som opptrer som Alice og programmet ditt som opptrer som Bob kjører samtidig. Tids- og minnegrensene måles som summen av alle tre, så la det være nok margin for både tids- og minnebruk.
- Dommerprogrammet bruker opptil omtrent $50$ ms og $5$ MiB.
- Du vil håndtere heltall i området $0$ til $2^{64} - 1$. Vær forsiktig med overflow.
Eksempler
Eksempelinndata 1
Alice 31 1
Eksempelutdata 1
send 0 receive send 1 answer 25
Eksempelinndata 2
Bob 25 0 1
Eksempelutdata 2
receive send 1 receive answer 25