Le circuit de la Batmobile

Course imprévisible dans une ville tirée au cordeau

La ville de Gotham est très bien structurée, en rues verticales et avenues horizontales régulièrement espacées. Il y a 99 rues et 99 avenues qui créent ainsi un réseau carré. Voici un exemple d'un tel réseau contenant uniquement 5 rues et avenues au lieu de 99.

plan de vilel style gotham

À chaque carrefour, un panneau indique quelle direction prendre. À chaque fois que la Batmobile arrive à un carrefour, elle prend la direction indiquée par le panneau et, par l'intermédiaire d'une télécommande, fait tourner le panneau vers la direction suivante, dans le sens des aiguilles d'une montre : un panneau indiquant le nord indiquera l'est, un panneau est deviendra sud, un panneau sud deviendra ouest....

Si pour la plupart des carrefours, les 4 directions sont possibles, ce n'est pas le cas pour les carrefours situés en bordure de ville. En aucun cas un panneau ne peut indiquer une direction qui ferait sortir de la ville. Ainsi, au carrefour du coin nord ouest (à l'angle de la première rue et de la première avenue), le panneau ne peut prendre que les directions est ou sud. À chaque passage de la Batmobile, il oscillera donc entre ces deux directions. De même à l'angle de la première rue et de la troisième avenue (un carrefour situé à la limite ouest de la ville donc), le panneau ne peut prendre que les directions est, sud et nord.

Batman commence sa tournée en plein cœur de la ville au croisement de la 50e rue et de la 50e avenue. En comptant ce carrefour initial, il va visiter 1000 carrefours, qui ne seront pas forcément tous différents (il arrivera qu'il repasse par un carrefour déjà visité).

Le parcours de la Batmobile est plus ou moins erratique, et Batman espère ainsi être imprévisible.

Pour relever le défi, vous devez indiquer (dans l'ordre ci-dessous) :

  • combien de carrefours différents il visitera,
  • le plus petit et le plus grand numéro de rue de son trajet,
  • le plus petit et le plus grand numéro d'avenue de son trajet.

Le plan de la ville et les positions initiales des panneaux sont visibles en suivant le lien dans la rubrique "Entrée du problème". Les directions Nord, Sud, Est ou Ouest des panneaux sont indiquées par l'initiale du point cardinal.

Exemple

Voyons ce que cela donne pour une ville plus petite, contenant 5 rues et 5 avenues qui serait décrite ainsi :

ESESS
NOEON
NOEEO
NONEN
EONON

Dans les figures suivantes, la Batmobile est symbolisée par le carré bleu, qui part du centre de la ville. Observez ses déplacements et les rotations des panneaux de direction :

La Batmobile se promène

Ainsi, au bout de 7 déplacements (au lieu de 1000), la Batmobile sera passée par 6 carrefours différents, situés entre la 3e et la 5e rue et entre la 2e et la 4e avenue. Pour valider le défi dans ce cas, il faudrait donc répondre : 6, 3, 5, 2, 4

Attention, pensez que la batmobile part du centre de la ville (soit la 50e rue, 50e avenue pour une ville de 99 rues et 99 avenues).

Ce problème est tiré de c0d1ng UP 2016

Type de retour

une séquence de 5 entiers

Entrée du problème

Lien vers les données d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup16 simulation