Detta är ett kommunikationsproblem.
Två program, Alice och Bob, spelar följande samarbetsspel.
Du får heltalen $A$ och $B$ med $0 \le A, B < 2^{64}$. Till en början känner endast Alice till $A$, och endast Bob känner till $B$. Låt $C := \min(A, B)$. Målet är att både Alice och Bob ska kunna skriva ut $C$.
För att utbyta information får Alice och Bob anropa följande funktioner:
send(x): Skicka ett 1-bitsvärde $x$ till det andra programmet. Detta anrop returnerar inte förrän det andra programmet anroparreceive().receive(): Ta emot ett 1-bitsvärde från det andra programmet och returnera det. Detta anrop returnerar inte förrän det andra programmet anroparsend().
Det totala antalet anrop till send() som görs av Alice och Bob tillsammans får inte överstiga $76$. Detsamma gäller för receive().
När kommunikationen är avslutad måste varje program anropa följande funktion exakt en gång:
answer(x): Deklarera att värdet på $C$ är $x$. Omedelbart efter att denna funktion anropats måste programmet avslutas.
Spelet lyckas om både Alice och Bob svarar $C$ korrekt.
Skriv två program, Alice och Bob, som alltid lyckas i spelet.
Interaktionsprotokoll
Detta är ett interaktivt kommunikationsproblem (dina program och domaren kommunicerar via standard in-/utdata). Ditt program som agerar som Alice och ditt program som agerar som Bob kommer att spela spelet via domaren.
Programstart
Ditt program tar först emot indata i följande format:
Player X
Här är Player strängen Alice eller Bob, och $X$ är ett heltal med $0 \le X < 2^{64}$.
- Om
PlayerärAlice, så är $A = X$. Från och med nu måste ditt program agera som Alice. - Om
PlayerärBob, så är $B = X$. Från och med nu måste ditt program agera som Bob.
Anropa därefter send, receive och slutligen answer enligt beskrivningen nedan.
send
För att anropa send(x), skriv ut:
send x
Här måste $x$ vara $0$ eller $1$.
Detta anrop returnerar inte förrän det andra programmet anropar receive(). Du bedöms som Wrong Answer om något av följande inträffar:
- det andra programmet avslutas medan du väntar,
- det andra programmet anropar också
send()medan du väntar, - det totala antalet anrop till
send()av Alice och Bob överstiger $76$.
receive
För att anropa receive(), skriv ut:
receive
Läs sedan den mottagna biten $x$ från standardindata:
x
Detta anrop returnerar inte förrän det andra programmet anropar send(). Du bedöms som Wrong Answer om något av följande inträffar:
- det andra programmet avslutas medan du väntar,
- det andra programmet anropar också
receive()medan du väntar, - det totala antalet anrop till
receive()av Alice och Bob överstiger $76$.
Om du bedöms som Wrong Answer under interaktionen kommer indatan som ges att vara $-1$. Om du läser $-1$, avsluta ditt program omedelbart, annars kan du få Time Limit Exceeded.
answer
För att anropa answer(x), skriv ut:
answer x
Här måste $x$ vara lika med $\min(A, B)$. Avsluta ditt program omedelbart efter att ha anropat denna funktion.
Förklaring
- Efter varje utskrift måste ditt program tömma standardutdata (flush); annars kan du få Time Limit Exceeded.
- Domarprogrammet, ditt program som agerar som Alice och ditt program som agerar som Bob körs samtidigt. Tids- och minnesgränserna mäts som summan av alla tre, så lämna tillräcklig marginal för både tid och minne.
- Domarprogrammet förbrukar upp till cirka $50$ ms och $5$ MiB.
- Du kommer att hantera heltal i intervallet $0$ till $2^{64} - 1$. Var försiktig med overflow.
Exempel
Exempelindata 1
Alice 31 1
Exempelutdata 1
send 0 receive send 1 answer 25
Exempelindata 2
Bob 25 0 1
Exempelutdata 2
receive send 1 receive answer 25