Este es un problema de comunicación.
Dos programas, Alice y Bob, juegan al siguiente juego cooperativo.
Se dan dos enteros $A$ y $B$ con $0 \le A, B < 2^{64}$. Inicialmente, solo Alice conoce $A$ y solo Bob conoce $B$. Sea $C := \min(A, B)$. El objetivo es que tanto Alice como Bob puedan imprimir $C$.
Para intercambiar información, Alice y Bob pueden llamar a las siguientes funciones:
send(x): Envía un valor de 1 bit $x$ al otro programa. Esta llamada no retorna hasta que el otro programa llama areceive().receive(): Recibe un valor de 1 bit del otro programa y lo devuelve. Esta llamada no retorna hasta que el otro programa llama asend().
El número total de llamadas a send() realizadas entre Alice y Bob no debe superar $76$. Lo mismo se aplica a receive().
Una vez finalizada la comunicación, cada programa debe llamar exactamente una vez a la siguiente función:
answer(x): Declara que el valor de $C$ es $x$. Inmediatamente después de llamar a esta función, el programa debe terminar.
El juego tiene éxito si tanto Alice como Bob responden $C$ correctamente.
Escribe dos programas, Alice y Bob, que siempre tengan éxito en el juego.
Protocolo de interacción
Este es un problema de comunicación interactiva (tus programas y el juez se comunican mediante la entrada/salida estándar). Tu programa que actúa como Alice y tu programa que actúa como Bob jugarán la partida a través del juez.
Inicio del programa
Tu programa recibe primero la entrada con el siguiente formato:
Player X
Aquí, Player es la cadena Alice o Bob, y $X$ es un entero con $0 \le X < 2^{64}$.
- Si
PlayeresAlice, entonces $A = X$. A partir de este punto, tu programa debe comportarse como Alice. - Si
PlayeresBob, entonces $B = X$. A partir de este punto, tu programa debe comportarse como Bob.
Después de eso, llama a send, receive y finalmente a answer como se describe a continuación.
send
Para llamar a send(x), imprime:
send x
Aquí, $x$ debe ser $0$ o $1$.
Esta llamada no retorna hasta que el otro programa llama a receive(). Recibirás Wrong Answer si ocurre cualquiera de las siguientes situaciones:
- el otro programa termina mientras estás esperando,
- el otro programa también llama a
send()mientras estás esperando, - el número total de llamadas a
send()realizadas por Alice y Bob supera $76$.
receive
Para llamar a receive(), imprime:
receive
Luego lee el bit recibido $x$ de la entrada estándar:
x
Esta llamada no retorna hasta que el otro programa llama a send(). Recibirás Wrong Answer si ocurre cualquiera de las siguientes situaciones:
- el otro programa termina mientras estás esperando,
- el otro programa también llama a
receive()mientras estás esperando, - el número total de llamadas a
receive()realizadas por Alice y Bob supera $76$.
Si recibes Wrong Answer durante la interacción, la entrada proporcionada será $-1$. Si lees $-1$, termina tu programa de inmediato, o podrías recibir Time Limit Exceeded.
answer
Para llamar a answer(x), imprime:
answer x
Aquí, $x$ debe ser igual a $\min(A, B)$. Después de llamar a esta función, termina tu programa de inmediato.
Nota
- Después de cada salida, tu programa debe vaciar la salida estándar (flush); de lo contrario, podrías recibir Time Limit Exceeded.
- El programa juez, tu programa que actúa como Alice y tu programa que actúa como Bob se ejecutan simultáneamente. Los límites de tiempo y memoria se miden como la suma de los tres, así que deja suficiente margen tanto en tiempo como en memoria.
- El programa juez consume hasta unos $50$ ms y $5$ MiB.
- Manejarás enteros en el rango de $0$ a $2^{64} - 1$. Ten cuidado con el desbordamiento (overflow).
Ejemplos
Entrada de ejemplo 1
Alice 31 1
Salida de ejemplo 1
send 0 receive send 1 answer 25
Entrada de ejemplo 2
Bob 25 0 1
Salida de ejemplo 2
receive send 1 receive answer 25