Connaissez-vous la société Just Ordinary Inventions ? Son activité consiste à réaliser « des inventions tout simplement ordinaires ».

JOI-kun joue au tout dernier jeu développé par Just Ordinary Inventions.

Dans ce jeu, il faut explorer un donjon constitué de salles et de chemins. Chaque chemin relie deux salles différentes et peut être parcouru dans les deux sens. Deux salles différentes sont reliées par au plus un chemin, et aucun chemin n'a ses deux extrémités dans la même salle. On sait également qu'il est possible de se déplacer entre n'importe quelles deux salles du donjon en empruntant des chemins. Les salles se ressemblent énormément : deux salles ayant le même nombre de chemins sortants sont totalement indiscernables à leur seule apparence.

Pour faciliter le jeu, chaque salle contient un repère et un socle. Grâce au repère, les chemins sortant de la salle peuvent être numérotés $1,2,\ldots$. La structure du donjon ne change pas pendant la partie. Ainsi, emprunter un chemin de même numéro depuis une même salle conduit toujours à la même salle. Un joyau dont le joueur peut changer la couleur est posé sur le socle. Sa couleur est l'une des couleurs $1,2,\ldots,X$ ; au début de la partie, le joyau de chaque salle est de couleur $1$. La couleur d'un joyau ne change que si le joueur la modifie.

JOI-kun a compris que, s'il connaissait la structure du donjon, c'est-à-dire la façon dont ses salles sont reliées par les chemins, il pourrait facilement terminer le jeu. Malgré ses diverses tentatives, il n'a toutefois pas réussi à déterminer cette structure. Vous avez donc décidé d'écrire à sa place un programme qui la détermine.

Tâche

Écrivez un programme qui explore le donjon et détermine sa structure. Cependant, JOI-kun ne souhaite pas que celle-ci lui soit entièrement révélée. Au lieu de donner directement la structure du donjon, votre programme doit donc répondre, pour chaque entier $i$ compris entre $1$ et $R$, à la question : « Combien y a-t-il de paires de salles dont le trajet le plus court utilise exactement $i$ chemins ? » Inverser l'ordre des deux salles donne la même paire.

Une bibliothèque vous est fournie pour effectuer les actions suivantes afin d'explorer le donjon.

• Connaître le nombre de chemins sortant de la salle actuelle.
• Connaître la couleur du joyau posé sur le socle de la salle actuelle.
• Donner au joyau de la salle actuelle une couleur spécifiée, éventuellement identique à sa couleur actuelle, puis choisir un chemin sortant de cette salle et l'emprunter pour rejoindre une autre salle.
• Connaître le numéro du dernier chemin emprunté parmi les chemins sortant de la salle actuelle.

Détails d'implémentation

Vous devez écrire un programme qui implémente une méthode pour répondre à JOI-kun. Il doit inclure dungeon2.h.

Votre programme doit implémenter la routine suivante.

• void Inspect(int R)

Cette routine est appelée une seule fois, au début.

• Le paramètre R indique que vous devez donner, pour chaque entier $i$ compris entre $1$ et $R$, le nombre de paires de salles dont le trajet le plus court utilise exactement $i$ chemins. Inverser l'ordre des salles donne la même paire.

Vous devez également appeler la routine suivante pour fournir vos réponses.

• void Answer(int D, int A)

• Les paramètres D et A indiquent que cet appel répond : « Il existe $A$ paires de salles dont le trajet le plus court utilise exactement $D$ chemins. »

Les appels à Answer doivent respecter les conditions suivantes.

• D doit être un entier compris entre $1$ et $R$. Sinon, le verdict est Wrong Answer [1].
• Vous ne devez pas appeler Answer plusieurs fois avec la même valeur de D. Sinon, le verdict est Wrong Answer [2].
• Vous devez appeler Answer exactement $R$ fois. Sinon, le verdict est Wrong Answer [3].
• A doit être le nombre de paires de salles dont le trajet le plus court utilise exactement $D$ chemins. Sinon, le verdict est Wrong Answer [4].

Lorsqu'un appel à Answer est jugé incorrect, la poursuite de l'exécution du programme n'est pas garantie.

Vous pouvez en outre appeler les routines suivantes.

• void Move(int I, int C)

• Le paramètre I est le numéro du chemin choisi pour le déplacement. Immédiatement après cet appel, le joueur emprunte le $I$-ième chemin sortant de la salle actuelle pour rejoindre une autre salle.

• Le paramètre C indique qu'avant de changer de salle, le joueur donne la couleur $C$ au joyau posé sur le socle de la salle actuelle.

Les appels à Move doivent respecter les conditions suivantes.

• Si $K$ est le nombre de chemins sortant de la salle actuelle, I doit être un entier compris entre $1$ et $K$. Sinon, le verdict est Wrong Answer [5].
• Si $X$ est le nombre de couleurs possibles, C doit être un entier compris entre $1$ et $X$. La valeur de $X$ dépend de la sous-tâche. Sinon, le verdict est Wrong Answer [6].

• Vous ne devez pas appeler Move plus de $1\,500\,000$ fois. Sinon, le verdict est Wrong Answer [7].

• int NumberOfRoads()

• Cette fonction renvoie le nombre de chemins sortant de la salle où se trouve actuellement le joueur.

• int LastRoad()

• Cette fonction renvoie le numéro du dernier chemin emprunté parmi les chemins sortant de la salle actuelle. Si elle est appelée avant tout appel à Move, elle renvoie $-1$.

• int Color()

• Cette fonction renvoie la couleur du joyau posé sur le socle de la salle où se trouve actuellement le joueur.

Les réponses sont vérifiées après l'appel à la routine Inspect.

Vous pouvez librement implémenter d'autres routines à usage interne et déclarer des variables globales. Cependant, votre programme ne doit en aucune manière communiquer avec l'entrée standard, la sortie standard ou d'autres fichiers.

Compilation et exécution

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

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

• En C :

gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm

• En C++ :

g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp

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

Attention : le véritable programme d'évaluation diffère de cet exemple. L'exemple est lancé comme un seul processus, lit les données sur l'entrée standard et écrit les résultats sur la sortie standard.

Entrée de l'exemple de programme d'évaluation

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

• La première ligne contient les entiers $N,X,R$, séparés par des espaces. Cela signifie que le donjon contient $N$ salles, appelées salles $1,2,\ldots,N$, que les joyaux peuvent avoir $X$ couleurs et que votre programme doit fournir $R$ valeurs.
• Parmi les $2N$ lignes suivantes, la ligne $2i-1$ ($1 \le i \le N$) contient l'entier $D_i$, indiquant que $D_i$ chemins sortent de la salle $i$. La ligne $2i$ ($1 \le i \le N$) contient les $D_i$ entiers $T_{i1},T_{i2},\ldots,T_{iD_i}$, séparés par des espaces. Emprunter le $j$-ième chemin ($1 \le j \le D_i$) sortant de la salle $i$ conduit à la salle $T_{ij}$.
• La $j$-ième des $R$ lignes suivantes ($1 \le j \le R$) contient l'entier $A_j$. Cela signifie qu'il existe $A_j$ paires de salles dont le trajet le plus court utilise exactement $j$ chemins. Autrement dit, pour chaque $j$ ($1 \le j \le R$), l'exemple de programme d'évaluation accepte un appel à Answer avec D égal à $j$ et A égal à $A_j$, et rejette toute autre réponse.

L'exemple de programme d'évaluation appelle votre routine en plaçant initialement le joueur dans la salle $1$.

Sortie de l'exemple de programme d'évaluation

Si l'exécution se termine normalement, l'exemple de programme d'évaluation écrit les informations suivantes sur une seule ligne de la sortie standard. Les guillemets ne sont pas écrits.

• Si la réponse est correcte, le nombre d'appels à Move est affiché sous une forme telle que « Accepted : #move = 8 ».
• Si la réponse est incorrecte, le type d'erreur est affiché sous une forme telle que « Wrong Answer [1] ».

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes. Pour la signification de $N,D_i,T_{ij}$, consultez la section « Entrée de l'exemple de programme d'évaluation ».

• $2 \le N \le 200$.
• $3 \le X \le 100$.
• $1 \le R \le 200$.
• $1 \le D_i \le N-1$ ($1 \le i \le N$).
• $1 \le T_{ij} \le N$ et $T_{ij} \ne i$ ($1 \le i \le N$, $1 \le j \le D_i$).
• Les valeurs $T_{i1},T_{i2},\ldots,T_{iD_i}$ sont deux à deux distinctes ($1 \le i \le N$).
• Pour chaque $i,j$ ($1 \le i \le N$, $1 \le j \le D_i$), il existe un $k$ ($1 \le k \le D_{T_{ij}}$) tel que $T_{T_{ij}k}=i$.
• Il est possible de se déplacer entre n'importe quelles deux salles en empruntant des chemins.

Sous-tâches

Dans ce qui suit, $N$ désigne le nombre de salles du donjon et $M$ le nombre de chemins dans les données d'entrée.

Sous-tâche 1 [17 points]

Les conditions suivantes sont satisfaites.

• $N \le 50$.
• $M \le 100$.
• $X=100$.

Sous-tâche 2 [27 points]

Les conditions suivantes sont satisfaites.

• $N \le 50$.
• $M \le 100$.
• $X=3$.

Sous-tâche 3 [56 points]

• $X=3$.

Le score de cette sous-tâche est déterminé comme suit.

• Soit $L$ le maximum, sur tous les cas de test de cette sous-tâche, de la valeur suivante :

  • $\dfrac{C}{M}$, où $C$ est le nombre d'appels à Move.

• Le score de cette sous-tâche vaut alors :

  • $56$ points si $L \le 14$ ;
  • $\lfloor 70-L \rfloor$ points si $14 < L \le 32$ ;
  • $\left\lfloor 54-\dfrac{L}{2} \right\rfloor$ points si $32 < L \le 64$ ;
  • $0$ point si $64 < L$.

Ici, $\lfloor x \rfloor$ désigne le plus grand entier inférieur ou égal à $x$.

Dans le système d'évaluation, lorsqu'un programme se termine correctement et que sa réponse est jugée correcte, Accepted apparaît dans la colonne des détails. Cependant, pour la sous-tâche 3, un cas de test où les valeurs $C,M$ ci-dessus vérifient $64 < \dfrac{C}{M}$ reçoit un verdict de réponse incorrecte dans la colonne des résultats.

Exemple d'interaction

Voici un exemple d'entrée lue par l'exemple de programme d'évaluation, ainsi que les appels correspondants aux routines.

Entrée 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Appels aux routines

Attention : les appels de fonctions de cet exemple ne sont pas nécessairement pertinents.