A et B, sélectionnés pour représenter le Japon à l'Olympiade internationale d'informatique, vont jouer au « jeu du messager » avec le président K du comité japonais de l'Olympiade d'informatique afin d'améliorer leurs compétences en traitement de l'information. Les règles de ce jeu sont décrites ci-dessous.

A et B sont isolés dans des pièces, comme sur le schéma. Les pièces de A, de B et du président K disposent chacune d'un téléphone interne, mais seul le président K peut passer des appels. Tout autre moyen de communication est coupé, et A et B ne peuvent pas quitter leur pièce sans en recevoir l'ordre.

Pièce de A — long couloir — pièce du président K — long couloir — pièce de B.

Au début du jeu, le président K communique par téléphone à A un entier strictement positif $X$. Le but du jeu est que A transmette correctement la valeur de $X$ à B sans que A et B communiquent directement.

La pièce du président K contient une grille de $4\times4$ cases. On note $(i,j)$ la case de la ligne $i$ et de la colonne $j$ ($1 \le i \le 4$, $1 \le j \le 4$). La case $(1,1)$ est dans le coin supérieur gauche, $(1,4)$ dans le coin supérieur droit, $(4,1)$ dans le coin inférieur gauche et $(4,4)$ dans le coin inférieur droit. Au début du jeu, un pion est placé sur l'une des cases. Par la suite, le président K ne change jamais la case sur laquelle se trouve le pion.

Le président K appelle ensuite à plusieurs reprises A ou B par téléphone pour le faire venir dans sa pièce. À chaque visite, A ou B doit déplacer le pion sur une case immédiatement au-dessus, au-dessous, à gauche ou à droite. Après le déplacement, la personne retourne dans sa pièce. Si B connaît la valeur de $X$ lorsqu'il vient dans la pièce du président K, il peut la lui annoncer au lieu de déplacer le pion. Si la valeur annoncée est correcte, la réponse est acceptée ; sinon, elle est incorrecte.

Les moments auxquels le président K fait venir A ou B sont irréguliers, et A et B ignorent l'ordre dans lequel ils sont appelés. Toutefois, le président K fixe cet ordre au début du jeu, et il est garanti qu'il ne fait jamais venir l'une des deux personnes plus de $100$ fois de suite. Si B n'a toujours pas annoncé la valeur de $X$ lorsque A ou B retourne dans sa pièce après un total de $10\,000$ visites, le jeu se termine par une réponse incorrecte.

Tâche

Implémentez les stratégies de A et B dans des programmes permettant d'obtenir une réponse correcte au « jeu du messager » décrit ci-dessus.

Détails d'implémentation

Vous devez soumettre deux fichiers écrits dans le même langage de programmation.

Le premier fichier s'appelle playerA.c ou playerA.cpp. Il implémente la stratégie de A et doit implémenter les routines suivantes.

void InitA(int T, int X)

Cette routine est appelée une seule fois au début. Le paramètre $T$ est le numéro de sous-tâche, et $X$ est l'entier strictement positif que A doit transmettre à B.

int GameA(int I, int J)

Cette routine est appelée lorsque A vient dans la pièce du président K. Les paramètres $I,J$ sont la paire d'entiers $(I,J)$ indiquant la case où se trouve le pion à l'arrivée de A. Ils satisfont $1 \le I \le 4$ et $1 \le J \le 4$.

Cette routine doit renvoyer l'un des entiers $-1,-2,-3,-4$. Si elle renvoie une autre valeur, le programme est jugé incorrect [1] et son exécution est arrêtée. Ces valeurs indiquent que A effectue les actions suivantes.

• $-1$ : déplacer le pion sur la case du dessus $(I-1,J)$.
• $-2$ : déplacer le pion sur la case du dessous $(I+1,J)$.
• $-3$ : déplacer le pion sur la case de gauche $(I,J-1)$.
• $-4$ : déplacer le pion sur la case de droite $(I,J+1)$.

Si le déplacement demandé fait sortir le pion de la grille, le programme est jugé incorrect [2] et son exécution est arrêtée.

Le second fichier s'appelle playerB.c ou playerB.cpp. Il implémente la stratégie de B et doit implémenter les routines suivantes.

void InitB(int T)

Cette routine est appelée une seule fois au début. Le paramètre $T$ est le numéro de sous-tâche.

int GameB(int I, int J)

Cette routine est appelée lorsque B vient dans la pièce du président K. Les paramètres $I,J$ sont la paire d'entiers $(I,J)$ indiquant la case où se trouve le pion à l'arrivée de B. Ils satisfont $1 \le I \le 4$ et $1 \le J \le 4$.

Cette routine doit renvoyer l'un des entiers $-1,-2,-3,-4$ ou un entier strictement positif $Y$. Si elle renvoie une autre valeur, le programme est jugé incorrect [3] et son exécution est arrêtée. Ces valeurs indiquent que B effectue les actions suivantes.

• $-1$ : déplacer le pion sur la case du dessus $(I-1,J)$.
• $-2$ : déplacer le pion sur la case du dessous $(I+1,J)$.
• $-3$ : déplacer le pion sur la case de gauche $(I,J-1)$.
• $-4$ : déplacer le pion sur la case de droite $(I,J+1)$.

Si le déplacement demandé fait sortir le pion de la grille, le programme est jugé incorrect [4] et son exécution est arrêtée.

• Un entier strictement positif $Y$ : annoncer au président K que la valeur de $X$ est $Y$. Si $X=Y$, la réponse est acceptée ; sinon, le programme est jugé incorrect [5]. Dans les deux cas, son exécution est arrêtée.

L'une des routines GameA et GameB n'est jamais appelée plus de $100$ fois de suite. Si GameB n'a pas renvoyé d'entier strictement positif après un total de $10\,000$ appels à GameA et GameB, le programme est jugé incorrect [6] et son exécution est arrêtée.

Vous pouvez implémenter d'autres routines ou déclarer des variables globales pour un usage interne. Toutefois, les deux programmes soumis sont liés avec l'évaluateur pour former un seul exécutable. Vous devez donc déclarer static toutes les variables globales et routines internes de chaque fichier pour éviter les conflits avec les autres fichiers. Lors de l'évaluation, le programme est exécuté dans deux processus distincts, l'un pour A et l'autre pour B ; ils ne peuvent donc pas partager leurs variables globales.

Votre programme ne doit communiquer par aucun moyen avec l'entrée standard, la sortie standard ou d'autres fichiers.

Compilation et exécution

L'archive téléchargeable sur le site du concours contient un évaluateur d'exemple pour tester votre programme. Elle contient également des exemples des fichiers à soumettre.

L'évaluateur d'exemple se compose d'un seul fichier, grader.c ou grader.cpp. Pour tester votre programme, exécutez les commandes suivantes.

• En C :

gcc -O2 -lm grader.c playerA.c playerB.c -o grader

• En C++ :

g++ -O2 -lm grader.cpp playerA.cpp playerB.cpp -o grader

Si la compilation réussit, un exécutable appelé grader est créé.

L'évaluateur réel est différent de l'évaluateur d'exemple. Ce dernier est exécuté dans un seul processus, lit les données sur l'entrée standard et écrit les résultats sur la sortie standard.

Entrée

L'évaluateur d'exemple lit les données suivantes sur l'entrée standard.

• La première ligne contient les entiers $T,X,I_0,J_0$ séparés par des espaces. Ils indiquent le numéro de sous-tâche $T$, l'entier $X$ que A doit transmettre à B et la position initiale du pion $(I_0,J_0)$.
• La deuxième ligne contient une chaîne de longueur exactement $10\,000$, composée des caractères A et B. Si son caractère $k$ ($1 \le k \le 10\,000$) est A ou B, la routine appelée en $k$-ième position après les appels à InitA et InitB est respectivement GameA ou GameB.

Sortie

Si l'exécution se termine normalement, l'évaluateur d'exemple écrit les informations suivantes en une ligne sur la sortie standard.

• Si la réponse est correcte, il affiche Accepted (les guillemets ne sont pas imprimés ; il en va de même ci-dessous).
• Si la réponse est incorrecte, il affiche le type d'erreur avec le numéro défini dans la section « Détails d'implémentation », par exemple Wrong Answer [1]. Pour une réponse incorrecte [5], il affiche également la vraie valeur de $X$ et l'entier strictement positif $Y$ renvoyé par GameB, par exemple Wrong Answer [5] : X = 2, Y = 3.

Contraintes

Toutes les données d'entrée satisfont la condition suivante.

• $1 \le X \le 1\,000\,000\,000$.

Sous-tâches

Sous-tâche 1 [20 points]

• $T=1$.
• A est la première personne appelée dans la pièce du président K, puis A et B sont appelés en alternance. Autrement dit, après les appels à InitA et InitB, les routines sont appelées dans l'ordre GameA, GameB, GameA, GameB, ....

Sous-tâche 2 [20 points]

• $T=2$.
• La position initiale du pion est $(I_0,J_0)=(1,1)$. Autrement dit, après les appels à InitA et InitB, le premier appel à GameA ou GameB a pour paramètres $I=1,J=1$.

Sous-tâche 3 [60 points]

• $T=3$.

Exemple de communication

Voici un exemple d'entrée lu par l'évaluateur d'exemple et les appels de routines correspondants.

Entrée 1

2 6 1 1
ABBAABAAABBBBBABBAABBBABBBBAAAAABABAABAABBBBABAAAA

(La suite de la deuxième ligne est omise.)

Appels de l'exemple

Cet exemple ne décrit pas nécessairement une communication qui ait un sens.