N sacs sont disposés de manière arbitraire parmi les 2N cases d'une bande circulaire, c'est-à-dire un ensemble de cases telle que la première case se trouve en fait à côté de la dernière. Votre objectif est de programmer un robot qui déplace les sacs de sorte qu'il n'y ait plus deux sacs côte à côte. Notez en particulier qu'il ne doit pas y avoir à la fois un sac sur la première et un sac sur la dernière case.

Pour programmer le robot, vous disposez des fonctions suivantes :

• nbSacs() : retourne le nombre de sacs, qui est aussi égal à la moitié du nombre de cases.
• sacDansCase() : retourne vrai (ou 1 en C/C++) si la case où se trouve le robot contient un sac, et faux (ou 0 en C/C++) sinon.
• avance(nbCases) : déplace le robot vers la droite d'un certain nombre de cases.
• recule(nbCases) : déplace le robot vers la gauche d'un certain nombre de cases.
• ramasse() : si le robot ne porte pas de sac, alors il prend celui de sa case actuelle.
• pose() : si le robot porte un sac et que sa case actuelle n'en contient pas, alors il dépose le sac.

Vous pouvez visualiser ci-dessus l'exécution du programme suivant :

   avance(2)
   ramasse()
   recule(3)
   pose()
   avance(4)
   si (sacDansCase())
      avance(1)
   ramasse()
   avance(1)
   pose()

Écrivez un programme qui déplace les sacs de telle sorte que deux sacs ne soient jamais côte à côte.

Calcul du score

Votre programme sera exécuté sur 10 configurations initiales des sacs, avec 30 sacs au maximum dans chaque configuration (donc 60 cases au maximum). Votre programme doit fonctionner sur toute configuration de ce type, et pas seulement sur les configurations testées.

Pour chaque configuration, vous n'aurez des points que si vous séparez bien tous les sacs. Si le robot parcourt la distance la plus petite possible en portant un sac, vous aurez 100% des points. Sinon, chaque déplacement d'une case en trop (en portant un sac) vous fera perdre 10% des points, dans la limite de 50% des points. Notez que la distance parcourue lorsque le robot ne porte pas de sac n'a pas d'influence sur le score.

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(2);
   ramasse();
   recule(3);
   pose();
   avance(4);
   if (sacDansCase()) {
      printf("Sac dans la case !\n");
      avance(1);
   }
   ramasse();
   avance(1);
   pose();

   return 0;
}

#include "robot.h"
#define repeat(nb) for(int _loop = 1, _max = (nb) ; _loop <= _max ; _loop++)
 
int main() {
   avance(2);
   ramasse();
   recule(3);
   pose();
   avance(4);
   if (sacDansCase()) {
      printf("Sac dans la case !\n");
      avance(1);
   }
   ramasse();
   avance(1);
   pose();

   return 0;
}

open Robot;;

avance(2);
ramasse();
recule(3);
pose();
avance(4);
if sacDansCase() then begin
   Printf.printf "Sac dans la case !\n";
   avance(1);
end;
ramasse();
avance(1);
pose();

import static algorea.Robot.*;
  
class Main
{
   public static void main(String[] args)
   {
   avance(2);
   ramasse();
   recule(3);
   pose();
   avance(4);
   if (sacDansCase()) {
      System.out.println("Sac dans la case !\n");
      avance(1);
   }
   ramasse();
   avance(1);
   pose();
}

void main() {
   avance(2);
   ramasse();
   recule(3);
   pose();
   avance(4);
   if (sacDansCase()) {
      System.out.println("Sac dans la case !\n");
      avance(1);
   }
   ramasse();
   avance(1);
   pose();
}

from robot import *

avance(2)
ramasse()
recule(3)
pose()
avance(4)
if (sacDansCase()):
   print("Sac dans la case !")
   avance(1) 
ramasse()
avance(1)
pose()