Universal Cup Judging System

Universal Cup

実行時間制限: 0.5 s メモリ制限: 1024 MB 満点: 100 コミュニケーション
統計

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 chiama receive().
  • receive(): Riceve un valore a 1 bit dall'altro programma e lo restituisce. Questa chiamata non ritorna finché l'altro programma non chiama send().

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

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.