Challenge 3 : vaisseau téléporteur

Saurez-vous habilement piloter le vaisseau spatial au travers des tunnels sinueux ?

Vous pouvez obtenir la description d'un tunnel à l'aide des fonctions suivantes :

  • nbColonnes() retourne le nombre de colonnes du parcours, les colonnes étant numérotées à partir de 0.
  • nbLignes() retourne le nombre de hauteurs de vol possibles, les hauteurs étant numérotées à partir de 0.
  • hauteurMin(colonne) retourne la hauteur minimale à laquelle le vaisseau peut voler lorsqu'il se trouve à la colonne indiquée.
  • hauteurMax(colonne) retourne la hauteur maximale à laquelle le vaisseau peut voler lorsqu'il se trouve à la colonne indiquée.

Pour piloter le vaisseau, vous disposez de deux commandes :

  • avance(colonnes) déplace le vaisseau vers la droite du nombre de colonnes indiqué, sans changer de hauteur.
  • teleporte(hauteur) déplace verticalement le vaisseau jusqu'à la hauteur indiquée, sans changer de colonne.

Le vaisseau se trouve initialement à la hauteur 0, sur la colonne 0. Écrivez un programme qui le pilote jusqu'à n'importe quelle ligne de la dernière colonne, en effectuant le plus petit nombre de téléportations possible.

Vous pouvez visualiser ci-dessus l'effet du programme suivant :

      teleporte(3)
      avance(3)
      teleporte(5)
      avance(4)
      teleporte(3)
      avance(4)
   

Score

Votre programme sera exécuté sur 10 tunnels différents, dont la hauteur ne dépassera pas 30 lignes, et qui seront composés de 10 à 60 colonnes. Le premier des tunnels sera exactement celui présenté ci-dessus. Notez que votre programme doit pouvoir fonctionner sur toutes les configurations de ce type, et pas seulement sur les configurations testées.

Pour chaque configuration testée, vous n'aurez des points que si le vaisseau traverse le tunnel. Si le vaisseau effectue le nombre minimum de téléportations, vous aurez 100% des points. Sinon, chaque téléportation en trop vous fera perdre 5% des points, dans la limite de 50% des points.

Programmes d'exemple

Voici pour chaque langage, le programme complet effectuant les commandes listées ci-dessus, et dont vous pouvez partir. Notez que votre programme peut afficher du texte.

#include "robot.h"
#define repeat(nb) for(int _loop = 1, _max = (nb) ; _loop <= _max ; _loop++)

int main() {
   int nbCols = nbColonnes();
   int nbLins = nbLignes();
   teleporte(3);
   avance(3);
   teleporte(hauteurMin(5));
   avance(4);
   printf("au plafond");
   teleporte(hauteurMax(8));
   avance(4);
   return 0;
}
#include "robot.h"
#define repeat(nb) for(int _loop = 1, _max = (nb) ; _loop <= _max ; _loop++)

int main() {
   int nbCols = nbColonnes();
   int nbLins = nbLignes();
   teleporte(3);
   avance(3);
   teleporte(hauteurMin(5));
   avance(4);
   printf("au plafond");
   teleporte(hauteurMax(8));
   avance(4);
   return 0;
}
open Robot;;
  
let nbCols = nbColonnes() in
let nbLins = nbLignes() in
teleporte(3);
avance(3);
teleporte(hauteurMin(5));
avance(4);
Printf.printf "au plafond";
teleporte(hauteurMax(8));
avance(4);

import static algorea.Robot.*;
  
class Main
{
   public static void main(String[] args)
   {
      int nbCols = nbColonnes();
      int nbLins = nbLignes();
      teleporte(3);
      avance(3);
      teleporte(hauteurMin(5));
      avance(4);
      printf("au plafond");
      teleporte(hauteurMax(8));
      avance(4);
   }
}
void main() {
   int nbCols = nbColonnes();
   int nbLins = nbLignes();
   teleporte(3);
   avance(3);
   teleporte(hauteurMin(5));
   avance(4);
   println("au plafond");
   teleporte(hauteurMax(8));
   avance(4);
}

from robot import *
  
nbCols = nbColonnes()
nbLins = nbLignes()
teleporte(3)
avance(3)
teleporte(hauteurMin(5))
avance(4)
print("au plafond")
teleporte(hauteurMax(8))
avance(4)


Source : http://www.france-ioi.org/