Universal Cup Judging System

Universal Cup

時間限制: 0.5 s 記憶體限制: 1024 MB 總分: 100 通信
统计

Ceci est un problème de communication.

Deux programmes, Alice et Bob, jouent au jeu coopératif suivant.

On vous donne deux entiers $A$ et $B$ tels que $0 \le A, B < 2^{64}$. Initialement, seule Alice connaît $A$, et seul Bob connaît $B$. Soit $C := \min(A, B)$. L'objectif est qu'Alice et Bob puissent tous deux afficher $C$.

Pour échanger des informations, Alice et Bob peuvent appeler les fonctions suivantes :

  • send(x) : Envoyer une valeur sur 1 bit $x$ à l'autre programme. Cet appel ne se termine pas tant que l'autre programme n'appelle pas receive().
  • receive() : Recevoir une valeur sur 1 bit de l'autre programme et la renvoyer. Cet appel ne se termine pas tant que l'autre programme n'appelle pas send().

Le nombre total d'appels à send() effectués par Alice et Bob combinés ne doit pas dépasser $76$. Il en va de même pour receive().

Une fois la communication terminée, chaque programme doit appeler exactement une fois la fonction suivante :

  • answer(x) : Déclarer que la valeur de $C$ est $x$. Immédiatement après avoir appelé cette fonction, le programme doit se terminer.

Le jeu est réussi si Alice et Bob répondent tous deux correctement $C$.

Écrivez deux programmes, Alice et Bob, qui réussissent toujours à ce jeu.

Protocole d'interaction

Il s'agit d'un problème de communication interactif (vos programmes et le juge communiquent via l'entrée/sortie standard). Votre programme jouant le rôle d'Alice et votre programme jouant le rôle de Bob joueront la partie par l'intermédiaire du juge.

Démarrage du programme

Votre programme reçoit d'abord une entrée au format suivant :

Player
X

Ici, Player est la chaîne Alice ou Bob, et $X$ est un entier tel que $0 \le X < 2^{64}$.

  • Si Player vaut Alice, alors $A = X$. À partir de ce moment, votre programme doit se comporter comme Alice.
  • Si Player vaut Bob, alors $B = X$. À partir de ce moment, votre programme doit se comporter comme Bob.

Ensuite, appelez send, receive, et enfin answer comme décrit ci-dessous.

send

Pour appeler send(x), affichez :

send x

Ici, $x$ doit valoir $0$ ou $1$.

Cet appel ne se termine pas tant que l'autre programme n'appelle pas receive(). Vous recevrez le verdict Wrong Answer si l'un des cas suivants se produit :

  • l'autre programme se termine pendant que vous attendez,
  • l'autre programme appelle également send() pendant que vous attendez,
  • le nombre total d'appels à send() effectués par Alice et Bob dépasse $76$.

receive

Pour appeler receive(), affichez :

receive

Lisez ensuite le bit reçu $x$ depuis l'entrée standard :

x

Cet appel ne se termine pas tant que l'autre programme n'appelle pas send(). Vous recevrez le verdict Wrong Answer si l'un des cas suivants se produit :

  • l'autre programme se termine pendant que vous attendez,
  • l'autre programme appelle également receive() pendant que vous attendez,
  • le nombre total d'appels à receive() effectués par Alice et Bob dépasse $76$.

Si vous recevez le verdict Wrong Answer pendant l'interaction, l'entrée fournie sera $-1$. Si vous lisez $-1$, terminez votre programme immédiatement, sinon vous risquez de recevoir Time Limit Exceeded.

answer

Pour appeler answer(x), affichez :

answer x

Ici, $x$ doit être égal à $\min(A, B)$. Après avoir appelé cette fonction, terminez votre programme immédiatement.

Note

  • Après chaque affichage, votre programme doit vider le tampon de sortie standard (flush) ; sinon, vous risquez de recevoir Time Limit Exceeded.
  • Le programme juge, votre programme jouant Alice et votre programme jouant Bob s'exécutent simultanément. Les limites de temps et de mémoire sont mesurées comme la somme des trois, laissez donc une marge suffisante tant pour le temps que pour la mémoire.
    • Le programme juge consomme jusqu'à environ $50$ ms et $5$ MiB.
  • Vous manipulerez des entiers compris entre $0$ et $2^{64} - 1$. Faites attention aux dépassements de capacité (overflow).

Exemples

Exemple d'entrée 1

Alice
31
1

Exemple de sortie 1

send 0
receive
send 1
answer 25

Exemple d'entrée 2

Bob
25
0
1

Exemple de sortie 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.