On dispose d'une grille carrée constituée de N lignes et de N colonnes, avec 1 <= N <= 40, comme illustré ci-dessous. Chaque case de la grille contient un entier entre 0 et 99, en respectant la règle suivante : la valeur contenue dans une case est toujours supérieure ou égale à la valeur de la case située à sa gauche (lorsque cette case existe), et est supérieure ou égale à la valeur de la case située juste au-dessus d'elle (lorsque cette case existe).

Au début, vous ne connaissez pas les valeurs contenues dans la grille : pour chaque case, il vous faut appeler une fonction si vous souhaitez en connaître le contenu. Étant donné la valeur d'un nombre caché quelque part dans la grille, et présent une seule fois dans celle-ci, votre objectif est de trouver la position de ce nombre dans la grille, en appelant un nombre minimum de fois la fonction permettant de révéler le contenu d'une case.

Vous disposez donc des fonctions suivantes :

• tailleCarre() : retourne la valeur de N, qui est égale au nombre de lignes et au nombre de colonnes de la grille.
• valeurCible() : retourne la valeur que l'on doit trouver dans la grille.
• valeurCase(lig, col) : retourne la valeur située dans la case située à la ligne lig et à la colonne col, ou -1 si les coordonnées sont en dehors de la grille.
• repondre(lig, col) : permet de fournir la position de la case contenant la valeur cible.

Remarque : les lignes sont numérotées de 0 à N-1 en partant du haut, et les colonnes sont numérotées de 0 à N-1 en partant de la gauche.

Dans l'exemple ci-dessous, le carré fait 8 cases de côté. La valeur cible à trouver est 7. Pour vous aider à comprendre, toutes les valeurs non découvertes sont montrées en gris après la première étape de l'exécution.

Vous pouvez visualiser ci-dessus l'exécution du programme suivant, qui vous montre comment vous pouvez utiliser ces commandes. Notez qu'il ne résout l'exemple que par chance car la cible se trouve sur la diagonale qu'il explore.

   col = 0
   lig = 0
   Tant que (valeurCase(lig, col) < valeurCible())
      col = col + 1
      lig = lig + 1
   repondre(lig, col)

Écrivez un programme qui, pour n'importe quelle grille satisfaisant la propriété décrite dans le sujet, et pour n'importe quelle valeur cible apparaissant au moins une fois dans la grille, détermine la position d'une case contenant cette valeur cible. Moins vous utilisez d'appels à valeurCase, et plus vous aurez de points.

Pour chaque test :

• Si vous trouvez une case contenant la valeur cible, vous aurez au moins 20 points, quel que soit le nombre d'appels à valeurCase.
• Si vous utilisez moins de N*N/2 appels à valeurCase, vous aurez au moins 40 points.
• Si vous utilisez moins de 2*N appels à valeurCase, vous aurez 100 points.

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"

int main()
{
   int col = 0;
   int lig = 0;
   while(valeurCase(lig, col) < valeurCible())
   {
      col = col + 1;
      lig = lig + 1;
   }
   repondre(lig, col);
   
   return 0;
}

#include "robot.h"

int main()
{
   int col = 0;
   int lig = 0;
   while(valeurCase(lig, col) < valeurCible())
   {
      col = col + 1;
      lig = lig + 1;
   }
   repondre(lig, col);
   
   return 0;
}

open Robot;;

let _ =
   let col = ref 0 in
   let lig = ref 0 in
   while valeurCase(!lig, !col) < valeurCible() do
      col := !col + 1;
      lig := !lig + 1;
   done;
   repondre(!lig, !col)

import static algorea.Robot.*;

class Main
{
   static public void main(String args[])
   {
      int col = 0;
      int lig = 0;
      while(valeurCase(lig, col) < valeurCible())
      {
         col = col + 1;
         lig = lig + 1;
      }
      repondre(lig, col);
   }
}

void main()
{
   int col = 0;
   int lig = 0;
   while(valeurCase(lig, col) < valeurCible())
   {
      col = col + 1;
      lig = lig + 1;
   }
   repondre(lig, col);
}

from robot import *

col = 0
lig = 0
while valeurCase(lig, col) < valeurCible():
   col = col + 1
   lig = lig + 1
repondre(lig, col)