Questo è un problema di comunicazione.
Due programmi, Alice e Bob, giocano al seguente gioco cooperativo.
Vengono dati due interi $A$ e $B$ con $0 \le A, B < 2^{64}$. Inizialmente, solo Alice conosce $A$ e solo Bob conosce $B$. Sia $C := \min(A, B)$. L'obiettivo è fare in modo che sia Alice che Bob siano in grado di stampare $C$.
Per scambiarsi informazioni, Alice e Bob possono chiamare le seguenti funzioni:
send(x): Invia un valore a 1 bit $x$ all'altro programma. Questa chiamata non ritorna finché l'altro programma non chiamareceive().receive(): Riceve un valore a 1 bit dall'altro programma e lo restituisce. Questa chiamata non ritorna finché l'altro programma non chiamasend().
Il numero totale di chiamate a send() effettuate complessivamente da Alice e Bob non deve superare $76$. Lo stesso vale per receive().
Una volta terminata la comunicazione, ciascun programma deve chiamare esattamente una volta la seguente funzione:
answer(x): Dichiara che il valore di $C$ è $x$. Immediatamente dopo aver chiamato questa funzione, il programma deve terminare.
Il gioco ha successo se sia Alice che Bob rispondono correttamente $C$.
Scrivi due programmi, Alice e Bob, che abbiano sempre successo nel gioco.
Protocollo di interazione
Questo è un problema di comunicazione interattiva (i tuoi programmi e il giudice comunicano tramite standard input/output). Il tuo programma che agisce come Alice e il tuo programma che agisce come Bob giocheranno la partita tramite il giudice.
Avvio del programma
Il tuo programma riceve inizialmente l'input nel seguente formato:
Player X
Qui, Player è la stringa Alice oppure Bob, e $X$ è un intero con $0 \le X < 2^{64}$.
- Se
PlayerèAlice, allora $A = X$. Da questo momento in poi, il tuo programma deve comportarsi come Alice. - Se
PlayerèBob, allora $B = X$. Da questo momento in poi, il tuo programma deve comportarsi come Bob.
Successivamente, chiama send, receive e infine answer come descritto di seguito.
send
Per chiamare send(x), stampa:
send x
Qui, $x$ deve essere $0$ oppure $1$.
Questa chiamata non ritorna finché l'altro programma non chiama receive(). Verrai giudicato Wrong Answer se si verifica una qualsiasi delle seguenti condizioni:
- l'altro programma termina mentre stai aspettando,
- anche l'altro programma chiama
send()mentre stai aspettando, - il numero totale di chiamate a
send()effettuate da Alice e Bob supera $76$.
receive
Per chiamare receive(), stampa:
receive
Poi leggi il bit ricevuto $x$ dallo standard input:
x
Questa chiamata non ritorna finché l'altro programma non chiama send(). Verrai giudicato Wrong Answer se si verifica una qualsiasi delle seguenti condizioni:
- l'altro programma termina mentre stai aspettando,
- anche l'altro programma chiama
receive()mentre stai aspettando, - il numero totale di chiamate a
receive()effettuate da Alice e Bob supera $76$.
Se vieni giudicato Wrong Answer durante l'interazione, l'input fornito sarà $-1$. Se leggi $-1$, termina immediatamente il programma, altrimenti potresti ricevere Time Limit Exceeded.
answer
Per chiamare answer(x), stampa:
answer x
Qui, $x$ deve essere uguale a $\min(A, B)$. Dopo aver chiamato questa funzione, termina immediatamente il programma.
Note
- Dopo ogni output, il tuo programma deve effettuare il flush dello standard output; altrimenti potresti ricevere Time Limit Exceeded.
- Il programma giudice, il tuo programma che agisce come Alice e il tuo programma che agisce come Bob vengono eseguiti simultaneamente. I limiti di tempo e di memoria sono misurati come la somma di tutti e tre, quindi lascia un margine sufficiente sia per il tempo che per la memoria.
- Il programma giudice consuma fino a circa $50$ ms e $5$ MiB.
- Gestirai interi nell'intervallo da $0$ a $2^{64} - 1$. Fai attenzione all'overflow.
Esempi
Input di esempio 1
Alice 31 1
Output di esempio 1
send 0 receive send 1 answer 25
Input di esempio 2
Bob 25 0 1
Output di esempio 2
receive send 1 receive answer 25