Challenge 2 : cadeau le plus lourd

Seize caisses sont disposées côte à côte. Chaque caisse, à l'exception des deux situées sur les bords, contient un cadeau d'un certain poids, comme illustré sur l'exemple plus bas. Tous les cadeaux ont des poids différents.

Votre objectif consiste à programmer un robot de sorte à ce qu'il récupère le cadeau le plus lourd et aille le déposer dans la caisse située tout à droite. Mais attention : le robot ne peut porter qu'un seul cadeau à la fois, et il ne peut comparer le poids de deux cadeaux que s'il porte l'un des deux cadeaux et qu'il se trouve devant la caisse contenant l'autre cadeau.

Pour programmer le robot, vous disposez donc des fonctions suivantes :

  • avance(nbCases) : déplace le robot vers la droite du nombre de cases indiqué.
  • recule(nbCases) : déplace le robot vers la gauche du nombre de cases indiqué.
  • prends() : si le robot ne porte pas de cadeau et que la caisse devant lui contient un cadeau, alors il ramasse ce cadeau, sinon il ne fait rien.
  • pose() : si le robot porte un cadeau et que la caisse devant lui est vide, alors il y dépose le cadeau qu'il porte, sinon il ne fait rien.
  • plusLourdDansCaisse() : retourne vrai (ou 1 en C/C++) si la caisse devant le robot contient un cadeau plus lourd que celui qu'il porte, ou si la caisse contient un cadeau mais le robot ne porte rien, et faux (ou 0 en C/C++) dans les autres cas.

Vous pouvez visualiser ci-dessus l'exécution du programme suivant, qui ne résout pas le problème mais montre comment vous pouvez utiliser ces commandes :

   avance(1)
   prends()
   avance(1)
   si (plusLourdDansCaisse())
      avance(1)
   recule(3)
   pose()
   répète 2 fois
      avance(1)
   prends()
   jette()

Écrivez un programme qui, quelle que soit la répartition des poids des cadeaux, fait en sorte que le robot dépose le plus lourd sur la case située tout à droite. Moins le robot parcourt de distance pendant qu'il porte un cadeau, et plus vous aurez de points.

Version simplifiée

Si vous trouvez le problème trop difficile, vous pouvez commencer par utiliser une fonction supplémentaire qui commande au robot de se débarrasser du cadeau qu'il porte, sans le remettre dans une des caisses. Cette fonction est :

  • jette() : si le robot porte un cadeau, alors il jette définitivement ce cadeau.

Score

La première des 7 configurations testées sera celle de l'exemple présenté ci-dessus, donc vous pourrez récupérer les points de cet exemple dès lors que votre programme fonctionne sur cette configuration particulière.

Si vous validez un test en utilisant la fonction jette(), vous aurez 40% des points sur ce test.

Si vous y arrivez sans utiliser la fonction jette(), votre score dépendra du nombre de déplacements effectués en portant un cadeau. Si le robot n'effectue pas plus de 28 déplacements en portant un cadeau, vous aurez 100% des points. Sinon, chaque déplacement en trop vous fera perdre 1% des points, dans la limite de 50% des points.

Notez que la distance parcourue lorsque le robot ne porte pas de cadeau n'a pas d'influence sur le score.

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() {
   avance(1);
   prends();
   avance(1);
   if (plusLourdDansCaisse()) {
      printf("Plus lourd dans la caisse !");
      avance(1);
   }
   recule(3);
   pose();
   repeat(2) {
      avance(1);
   }
   prends();
   jette();
 
   return 0;
}
#include "robot.h"
#define repeat(nb) for(int _loop = 1, _max = (nb) ; _loop <= _max ; _loop++)

int main() {
   avance(1);
   prends();
   avance(1);
   if (plusLourdDansCaisse()) {
      printf("Plus lourd dans la caisse !");
      avance(1);
   }
   recule(3);
   pose();
   repeat(2) {
      avance(1);
   }
   prends();
   jette();
 
   return 0;
}
open Robot;;
 
avance(1);
prends();
avance(1);
if plusLourdDansCaisse() then begin
   Printf.printf "Plus lourd dans la caisse !";
   avance(1);
end;
recule(3);
pose();
for loop = 1 to 2 do
   avance(1);
done;;
prends();
jette();
import static algorea.Robot.*;
  
class Main
{
   public static void main(String[] args)
   {
      avance(1);
      prends();
      avance(1);
      if (plusLourdDansCaisse()) {
         System.out.println("Plus lourd dans la caisse !");
         avance(1);
      }
      recule(3);
      pose();
      for (int loop = 1; loop <= 2; loop++) {
         avance(1);
      }
      prends();
      jette();
   }
}
void main() {
   avance(1);
   prends();
   avance(1);
   if (plusLourdDansCaisse()) {
      println("Plus lourd dans la caisse !");
      avance(1);
   }
   recule(3);
   pose();
   repeat(2) {
      avance(1);
   }
   prends();
   jette();
}
from robot import *
 
avance(1)
prends()
avance(1)
if (plusLourdDansCaisse()):
   print("Plus lourd dans la caisse !")
   avance(1)
recule(3)
pose()
for loop in range(2):
   avance(1)
prends()
jette()

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