Aujourd’hui vous allez jouer à voleur et gendarmes dans le métro parisien. Il s’agit d’une version simplifiée du jeu Scotland Yard où il y a un voleur et deux gendarmes qui se déplacent à tour de rôle.
Le métro consiste en 301 stations. Deux stations u,v sont voisines s’il est possible d’atteindre v à partir de u en voyageant le long d’une ligne particulière, sans qu’il n’y ait une autre station entre u et v. Par exemple Gare du Nord et Gare de l’Est sont voisines (par la ligne 5), alors que Saint Michel et Châtelet ne sont pas voisines (il faut d’abord passer par Cité par exemple).
L’ensemble des stations et la notion de voisinage constitue ce qu’on appelle un graphe. Le plan du métro réel contient des trajets qui ne peuvent se faire que dans une direction, comme sur la ligne 10 près de la porte d’Auteuil ou la boucle de la ligne 7bis près de Botzaris. Mais nous avons simplifié la réalité, et pour nous aujourd’hui, les déplacements sont possibles dans les deux directions. Notre graphe est donc “non orienté”, dans le sens que si une station u est voisine de v alors v est également voisine de u.
Les stations sont numérotées de 0 à 300 et représentent les sommets du graphe. On peut le représenter par des listes d’adjacence. Il s’agit alors d’un tableau graph où graph[u] est la liste des numéros des stations voisines à u. Vous allez coder ce graphe en dur dans votre programme, ou alors le lire d’un fichier texte.
Cette archive contient les données du graphe. Vous y trouverez dans le fichier metro.txt le graphe en mode texte avec nombre de sommets et nombre d’arêtes en première ligne, suivie par les arêtes, décrites une par ligne sous la forme u v avec la normalisation \(u < v\). Si vous préférez, nous vous avons également fourni le codage du graphe pour certains langages. Le fichier stations.txt donne la correspondance entre le numéro et le nom de la station, ce qui pourrait vous aider à choisir le point de départ d’un gendarme.
Votre première mission consiste à répondre à une suite de questions. Chaque question demande si deux stations données sont voisines. Écrivez un programme qui lit sur l’entrée standard les informations suivantes.
Par exemple, si votre programme commence par lire sur l’entrée standard les entiers 1 et 10, il devra répondre à 10 questions de l’exercice 1.
u v, séparés par un espace, compris entre 0 et 300. Pour chaque question vous devez afficher la réponse sur une ligne, à savoir \(1\) si \(u\) et \(v\) sont voisines et \(0\) sinon.Par exemple, si une question de l’exercice 1 correspond aux deux entiers 2 et 101, votre programme doit afficher 1 (car les stations 2 et 101 sont voisines). Si une autre question correspond aux entiers 3 et 18, votre programme doit afficher 0 (car ces deux stations ne sont pas voisines).
Pour ce premier exercice, le score attribué est de 1 point pour chaque réponse correcte. Le score maximum est donc de \(301 * 301\).
Il est important de penser à vider le tampon d’affichage après chaque affichage de votre programme sur la sortie standard. Demandez de l’aide si vous ne savez pas comment faire. Exemples pour certains languages.
| langage | affichage |
|---|---|
| C | printf(“%i %i”, i1, i2); fflush(stdout); |
| C++ avec using namespace std | cout << i1 << " " << i2 << endl << flush; |
| Java | System.out.println(i1+" "+i2); System.out.flush(); |
| OCaml | Printf.printf “%d %d%!” i1 i2 |
| Python | print(i1, i2, flush=True) |
Pour tester votre code avec notre juge, vous avez besoin de deux programmes (fournis par les organisateurs):
Un exécutable appelé juge_local : pour Linux, Windows, Mac x86, Mac Arm
Un script python interactive_runner.py qui connecte la sortie de votre code à l’entrée du juge et connecte la sortie du juge à l’entrée de votre code.1
Imaginons que votre programme est un fichier exécutable solution. Alors vous pouvez tester votre code par la commande suivante.
python interactive_runner.py ./juge_local 1 -- ./solutionL’argument 1 indique le numéro de l’exercice que vous voulez tester.
Si par contre votre code est écrit en Python par exemple, vous utiliserez la commande suivante.
python interactive_runner.py ./juge_local 1 -- python solution.pyUne fois un exercice passé, vous pouvez soumettre la (ou les) sources(s) de votre solution (sans binaire) contenant les explications pour construire votre programme sur le site suivant : Soumettre
Il est conseillé de soumettre à chaque exercice.
Un chemin est une suite de stations \(u_1,u_2,\ldots,u_\ell\), tel que \(u_i\) et \(u_{i+1}\) sont voisines pour tout \(1\leq i < \ell\). Un tel chemin relie \(u_1\) à \(u_\ell\) et a la longueur \(\ell-1\). La distance entre deux stations \(u,v\) est la longueur du plus court chemin qui les relie.
Pour votre deuxième mission, vous devez répondre à des questions de distances. Pour cet exercice, la première ligne lue par votre programme contient deux entiers \(2\) et \(k\). Les \(k\) lignes suivante contiennent chacune une question, à laquelle votre programme devra répondre avant de lire la ligne suivante. Chaque question se présente sous forme d’une ligne avec deux entiers \(u,v\) compris entre 0 et 300.
Soit \(d\) la distance entre \(u\) et \(v\). Dans le cas où \(d\ge 2\), affichez \(d\) et un entier \(w\) correspondant au numéro d’une station voisine de \(u\), qui est sur un plus court chemin de \(u\) à \(v\) (plusieurs réponses sont parfois possibles). Dans le cas où \(d\in\{0,1\}\), affichez \(d\) et \(v\).
Le score est de 1 point pour chaque réponse correcte. Le score maximal est donc de $ 301 * 301$.
Indice: les plus courts chemins dans un graphe non-orienté peuvent se calculer par un parcours en largeur du graphe.
Imaginons que le voleur soit à la place d’Italie. Ce n’est pas une bonne idée pour lui d’aller à Tolbiac, car il pourra être facilement coincé. Si le gendarme est à ses trousses, il n’y a pas moyen de s’échapper, car dans cette direction, le voleur ne peut atteindre que des terminus.
Définition récursive: Les terminus sont à éviter. Pour une station \(v\) avec \(d\) voisins, si au moins \(d-1\) stations voisines sont à éviter, alors \(v\) est également à éviter.
Pour cette troisième mission, vous devez déterminer les stations à éviter. Pour cet exercice, la première ligne lue par votre programme contient deux entiers \(3\) et \(k\). Chacune des \(k\) lignes suivantes contient un entier \(v\). Pour chacun vous devez afficher \(1\) si la station \(v\) est à éviter et \(0\) sinon.
Le score est 301 points pour chaque réponse correcte. Le score maximal est \(301 * 301\).
Le but des exercices suivants est de programmer les gendarmes qui feront face, dans un premier temps (exercice 4), à un voleur naïf puis (exercice 5) à un voleur avancé.
Stratégie du voleur naïf
À la première ronde le voleur choisit une station initiale, qui n’est ni occupée par un gendarme, ni à éviter. Ce choix sera varié au cours des différentes parties.
Puis à chaque ronde suivante, s’il est capturé, alors il ne bouge pas. Sinon il doit choisir une station voisine de sa position courante, qui n’est pas à éviter et qui maximise la distance avec le gendarme le plus proche. Si plusieurs stations satisfont cette propriété, alors le voleur choisit la station de plus petit numéro. Notez que le voleur ne peut pas rester sur place.
Stratégie du voleur avancé
Le voleur n’est plus complètement déterministe. À chaque correspondance il choisit aléatoirement la station suivante sans revenir sur ses pas. Cette limitation a été faite pour équilibrer le jeu.
Pour cet exercice, la première ligne lue par votre programme contient deux entiers \(4\), \(k\). Ici \(k\) représente le nombre de parties que vous allez jouer. Chaque partie consiste en au plus \(100\) rondes. Pour chaque ronde vous affichez les positions des gendarmes, et puis vous lisez un entier qui décrit la position du voleur.
Plus spécifiquement:
À la toute première ronde vous avez le choix de la station initiale des gendarmes. Ça pourrait être intéressant de les placer sur des correspondances par exemple Opéra et Nation.
Pour les rondes suivantes, vous pouvez laisser les gendarmes sur leur station actuelle ou les placer sur une station voisine.
Vous affichez sur une ligne les positions des deux gendarmes séparées par un espace.
Ensuite vous allez lire un entier \(v\).
Si \(v\) est \(-1\) alors vous avez capturé le voleur et la partie est terminée. Le score est \(101\) moins le nombre de rondes de cette partie, le tout multiplié par 10.
Si \(v\) est \(-2\) alors vous n’avez pas capturé le voleur, et le nombre maximum de rondes est atteint. La partie est terminée, et votre score est 0.
Si \(v\) est entre 0 et 300, alors \(v\) est la position actuelle du voleur.
Lors de la vérification de votre code par le juge juge_local, un fichier trace.html sera produit qui montre la trace des déplacements faits par le voleur et le gendarme dans la première partie.
Si vous voulez tester votre code seulement sur une partie particulière, alors vous pouvez donner le numéro de la partie en argument supplémentaire au juge local comme ici:
python interactive_runner.py ./juge_local 4 1 -- python solution.pyPour information: le juge produit une trace de la première partie dans un fichier trace.html. Les déplacements des gendarmes seront en bleu/vert et celui du voleur en rouge.
Pour cet exercice, la première ligne lue par votre programme contient deux entiers \(5\) et \(k\). Ici \(k\) représente le nombre de parties que vous allez jouer. Chaque partie consiste en au plus \(100\) rondes. Pour chaque ronde vous affichez les positions des gendarmes, et puis vous lisez un entier, qui décrit la position du voleur.
Plus spécifiquement:
Supposons que le voleur se trouve à la station \(v\) et qu’à l’étape précédente il était à la station \(u\). Soient \(v_1 \ldots v_d\) les stations voisines de \(v\) qui ne sont pas à éviter. Le voleur choisit alors avec une probabilité \(1/(d-1)\) une station \(v_i\) différente de \(u\).
Au premier choix, la probabilité est \(1/d\) pour chacun des voisins.
Si vous voulez tester votre code seulement sur une partie particulière, alors vous pouvez donner le numéro de la partie en argument supplémentaire au juge local comme ici:
python interactive_runner.py ./juge_local 5 1 -- python solution.pyNotez que le juge local utilise un générateur pseudo-aléatoire avec une graine de 0, et que nous allons évaluer votre code avec une graine différente. Le score sera calculé comme à l’exercice précédent.
Ce programme provient de l’ancienne compétition Google CodeJam.↩