Dies ist ein Kommunikationsproblem.
Zwei Programme, Alice und Bob, spielen das folgende kooperative Spiel.
Gegeben sind ganze Zahlen $A$ und $B$ mit $0 \le A, B < 2^{64}$. Zu Beginn kennt nur Alice den Wert $A$, und nur Bob kennt den Wert $B$. Sei $C := \min(A, B)$. Das Ziel ist es, dass sowohl Alice als auch Bob den Wert $C$ ausgeben können.
Um Informationen auszutauschen, dürfen Alice und Bob die folgenden Funktionen aufrufen:
send(x): Sende einen 1-Bit-Wert $x$ an das andere Programm. Dieser Aufruf kehrt erst zurück, wenn das andere Programmreceive()aufruft.receive(): Empfange einen 1-Bit-Wert vom anderen Programm und gib ihn zurück. Dieser Aufruf kehrt erst zurück, wenn das andere Programmsend()aufruft.
Die Gesamtzahl der Aufrufe von send() durch Alice und Bob zusammen darf $76$ nicht überschreiten. Dasselbe gilt für receive().
Nachdem die Kommunikation beendet ist, muss jedes Programm genau einmal die folgende Funktion aufrufen:
answer(x): Erkläre, dass der Wert von $C$ gleich $x$ ist. Unmittelbar nach dem Aufruf dieser Funktion muss sich das Programm beenden.
Das Spiel ist erfolgreich, wenn sowohl Alice als auch Bob den Wert $C$ korrekt angeben.
Schreibe zwei Programme, Alice und Bob, die in dem Spiel immer erfolgreich sind.
Interaktionsprotokoll
Dies ist ein interaktives Kommunikationsproblem (deine Programme und der Judge kommunizieren über die Standardein- und -ausgabe). Dein Programm in der Rolle von Alice und dein Programm in der Rolle von Bob spielen das Spiel über den Judge.
Programmstart
Dein Programm erhält zuerst eine Eingabe im folgenden Format:
Player X
Hierbei ist Player die Zeichenkette Alice oder Bob, und $X$ ist eine ganze Zahl mit $0 \le X < 2^{64}$.
- Wenn
PlayergleichAliceist, gilt $A = X$. Von diesem Zeitpunkt an muss sich dein Programm wie Alice verhalten. - Wenn
PlayergleichBobist, gilt $B = X$. Von diesem Zeitpunkt an muss sich dein Programm wie Bob verhalten.
Rufe danach wie unten beschrieben send, receive und schließlich answer auf.
send
Um send(x) aufzurufen, gib Folgendes aus:
send x
Hierbei muss $x$ gleich $0$ oder $1$ sein.
Dieser Aufruf kehrt erst zurück, wenn das andere Programm receive() aufruft. Du erhältst das Urteil Wrong Answer, wenn eines der folgenden Ereignisse eintritt:
- das andere Programm beendet sich, während du wartest,
- das andere Programm ruft ebenfalls
send()auf, während du wartest, - die Gesamtzahl der Aufrufe von
send()durch Alice und Bob überschreitet $76$.
receive
Um receive() aufzurufen, gib Folgendes aus:
receive
Lies anschließend das empfangene Bit $x$ von der Standardeingabe ein:
x
Dieser Aufruf kehrt erst zurück, wenn das andere Programm send() aufruft. Du erhältst das Urteil Wrong Answer, wenn eines der folgenden Ereignisse eintritt:
- das andere Programm beendet sich, während du wartest,
- das andere Programm ruft ebenfalls
receive()auf, während du wartest, - die Gesamtzahl der Aufrufe von
receive()durch Alice und Bob überschreitet $76$.
Falls dein Programm während der Interaktion als Wrong Answer gewertet wird, wird als Eingabe $-1$ bereitgestellt. Wenn du $-1$ einliest, beende dein Programm sofort, da du sonst Time Limit Exceeded erhalten kannst.
answer
Um answer(x) aufzurufen, gib Folgendes aus:
answer x
Hierbei muss $x$ gleich $\min(A, B)$ sein. Beende dein Programm unmittelbar nach dem Aufruf dieser Funktion.
Hinweis
- Nach jeder Ausgabe muss dein Programm die Standardausgabe leeren (flushen); andernfalls kannst du Time Limit Exceeded erhalten.
- Das Judge-Programm, dein Programm als Alice und dein Programm als Bob laufen gleichzeitig. Zeit- und Speicherlimit werden als Summe aller drei Prozesse gemessen, lasse also sowohl bei der Laufzeit als auch beim Speicherverbrauch genügend Spielraum.
- Das Judge-Programm verbraucht bis zu etwa $50$ ms und $5$ MiB.
- Du arbeitest mit ganzen Zahlen im Bereich von $0$ bis $2^{64} - 1$. Achte auf Überläufe (Overflow).
Beispiele
Beispieleingabe 1
Alice 31 1
Beispielausgabe 1
send 0 receive send 1 answer 25
Beispieleingabe 2
Bob 25 0 1
Beispielausgabe 2
receive send 1 receive answer 25