Un bug dans le chemin

Trouvez la baie pour soigner Parasect

Votre Pokémon Parasect a été empoisonné par un orbe toxique. Heureusement, un homme rencontré à Fort Vanitas vous a remis un parchemin qui doit vous mener à une Baie Pêcha, capable de guérir votre Pokémon.

Ce parchemin indique le chemin à suivre pour atteindre la baie. Il est composé d'une succession de lettres A, D et G et indique qu'on est initialement dirigé vers le nord.

  • la lettre A indique qu'il faut avancer de 100 mètres ;
  • la lettre D indique qu'il faut tourner d'un quart de tour sur sa droite (sans avancer) ;
  • la lettre G indique qu'il faut tourner d'un quart de tour sur sa gauche (sans avancer).

Par exemple, la série de lettres AGAADA correspond au trajet suivant : avancer de 100 m vers le nord, se tourner vers l'ouest, avancer de 200 m vers l'ouest, se tourner vers le nord, avancer de 100 m vers le nord.

Malheureusement, bien que vous ayez payé fort cher le parchemin, l'homme qui vous l'a remis vous dit en riant qu'il y a une erreur dans ce qu'il indique : une des lettres a été modifiée !

Ainsi, si le chemin indiqué avait été AGGAA, sachant qu'il comporte exactement une seule faute, le chemin correct aurait pu être :

GGGAA, DGGAA, ADGAA, AAGAA, AGDAA, AGAAA, AGGDA, AGGGA, AGGAD ou AGGAG

En traçant ces chemins, sur une carte, vous remarquez que ces 10 chemins peuvent vous mener dans 8 lieux différents (et non 10, car ADGAA et AGDAA mènent au même point, ainsi que AGGAD et AGGAG). Sur la figure ci-dessous, ces lieux sont marqués par les points noirs.

De plus, le trajet qui vous éloignera le plus est AGAAA, qui vous éloigne d'environ 316 mètres de votre point de départ.

Ayant pris connaissance de la séquence de lettres indiquée sur le parchemin (elle est donnée en entrée du problème), et ne sachant pas où est située l'erreur, vous désirez savoir combien de lieux différents il faudra visiter au maximum, si vous ne trouvez la baie qu'à la fin, et de combien vous vous éloignerez au plus de votre point de départ (vous devez arrondir à la valeur entière la plus proche).

Dans l'exemple, si le parchemin avait indiqué AGGAA, il aurait donc fallu donner comme réponse 8, 316

Ce problème est tiré de c0d1ng UP 2017

Type de retour

Deux nombres entiers

Entrée du problème

'ADDGAGDGGDDADDDGDADADGGGGGADGGDADAADAGGGDDADAAADGDDDDDAAAADDDDDDAGGAAAGGDAGAGADAADADAGDDDAAGGDGGAGAGDAGDGGDGAAGADGAAGDDADGDGDDGADAGAGDAGDAGDDDDGGDGGDAADDGGDAGADADGDDADAADDDAAAGGDGDGGGGADAGDGGGGADDDDDGDDDGAADGGDAAAAGDDDDADGADAGDAGDGAGAGGAADAGADADGGDADGGGGGGAGGDAGADGGADDGDAADGDGDDGDADADDDGAGGDDAGDDAAAGGAADDDGGGAAADGAGDGGAAAGAGAGGDAAAAGADDDDGAADADGDAGAAGGAADGADAGGDGAAAGGGDDAGDDDGADAAAGGAADAAADAAAGAGDDDDGAGGGGGDGGADAGAGAGAAGADADADGAGGDDGAAGGAADDDAGAAADADGAADADGGGAGAGDGGDAGDAGDGGAGGGADDDGDGAGGADDGDGA'

Formulaire de réponse

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

Tags : cup17 simulation géométrie