Vous avez retrouvé un stock de cartes perforées, que vous avez toutes scannées. Chaque carte contient un message constitué de lettres, codé dans une grille à 26 colonnes. Votre but va être de retrouver ce message.

Une carte perforée contient une grille, et chaque colonne de la grille correspond à une lettre de l'alphabet. L'encodage du message sur la carte a été effectué à la main à l'aide du procédé suivant :

• Les lettres du mot sont encodées une par une, dans l'ordre, chacune à l'aide d'un trou sur la carte. Les règles suivantes expliquent comment trouver la colonne et la ligne à laquelle faire le trou.
• La colonne dans laquelle on fait le trou est celle qui correspondant à la lettre. Pour A, on fait donc un trou à la première colonne, pour B à la seconde, pour Z à la dernière.
• Maintenant qu'on connaît la colonne, il faut trouver sur quelle ligne faire le trou. La règle est qu'on choisit la ligne où faire le trou de telle sorte :
  • qu'il n'y ait aucun trou déjà réalisé sur cette même ligne à droite de la colonne que l'on a sélectionnée,
  • qu'il n'y ait aucun trou sur les lignes d'en-dessous,
  • qu'on prenne la ligne la plus haute possible parmi celles qui respectent ces contraintes, de sorte à économiser du papier.
  Noter que ce système empêche de faire deux trous au même endroit.

Les cartes sont représentées dans un format texte. Les # représentent les cases non trouées, les lettres 'O' en majuscule représentent les trous. Voici par exemple les étapes de l'encodage du mot LETTRES :

ABCDEFGHIJKLMNOPQRSTUVWXYZ
###########O##############
Lettres placées: L

ABCDEFGHIJKLMNOPQRSTUVWXYZ
###########O##############
####O#####################
Lettres placées: LE

ABCDEFGHIJKLMNOPQRSTUVWXYZ
###########O##############
####O##############O######
Lettres placées: LET

ABCDEFGHIJKLMNOPQRSTUVWXYZ
###########O##############
####O##############O######
###################O######
Lettres placées: LETT

ABCDEFGHIJKLMNOPQRSTUVWXYZ
###########O##############
####O##############O######
###################O######
#################O########
Lettres placées: LETTR

ABCDEFGHIJKLMNOPQRSTUVWXYZ
###########O##############
####O##############O######
###################O######
#################O########
####O#####################
Lettres placées: LETTRE

ABCDEFGHIJKLMNOPQRSTUVWXYZ
###########O##############
####O##############O######
###################O######
#################O########
####O#############O#######
Lettres placées: LETTRES

• 1 <= N <= 1000, où N est le nombre de lignes de la grille.

• La première ligne de l'entrée contient un entier : le nombre de lignes de la grille, N.
• Les N lignes suivantes contiennent chacune 26 caractères. Chaque caractère est soit # (pas de trou), soit O (trou).

Vous devez écrire le mot codé par la carte, en lettres majuscules.

Nous vous proposons des indications pour lire l'entrée et afficher la sortie, en C/C++ et Caml, afin que vous ne risquiez pas d'être bloqué là-dessus. Il n'est pas du tout obligatoire de les utiliser.

Entrée-Sortie en C/C++

#include <stdio.h>

int main()
{
   int ligne, nbLignes;
   scanf("%d\n", &nbLignes);

   for (ligne = 0; ligne < nbLignes; ligne++) {

      // Lire toute la ligne d'un seul coup
      // dans un tableau de caractères
      char texteLigne[26 + 1];
      scanf("%s", texteLigne);

      // texteLigne[colonne] contient le caractère de la colonne donnée 
      // pour la ligne courante, pour colonne compris entre 0 et 25 inclus

      // Utiliser putchar(lettre); pour écrire une lettre

      ...
   }
   
   putchar('\n');
   return 0;
}

Entrée-Sortie en Caml

let nbLignes = Scanf.sscanf (read_line()) " %d" (fun x -> x);;

let _ =
   for ligne = 1 to nbLignes do

      (* Lire toute la ligne d'un seul coup dans une chaîne *)
      let texteLigne = read_line () in

      (* texteLigne.[colonne] contient le caractère de la colonne donnée 
         pour la ligne courante, pour colonne compris entre 0 et 25 inclus *)

      (* Utiliser "print_char lettre" pour écrire une lettre
         Utiliser char_of_int pour convertir un entier en caractère,
         par exemple: "print_char (char_of_int (int_of_char 'A' + 3))"
         pour écrire la lettre 'A' + 3, c'est-à-dire 'D' *)

      ...

   done;
   print_newline ()