Universal Cup Judging System

Universal Cup

Límite de tiempo: 0.5 s Límite de memoria: 1024 MB Puntuación total: 100 Comunicación
Estadísticas

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 a receive().
  • receive(): Recibe un valor de 1 bit del otro programa y lo devuelve. Esta llamada no retorna hasta que el otro programa llama a send().

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 Player es Alice, entonces $A = X$. A partir de este punto, tu programa debe comportarse como Alice.
  • Si Player es Bob, 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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.