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 pasreceive().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 passend().
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
PlayervautAlice, alors $A = X$. À partir de ce moment, votre programme doit se comporter comme Alice. - Si
PlayervautBob, 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