Olympiade d'Informatique de Madagascar

Entrainement > Eliminatoire 2008

Coincé !

Suite à un naufrage, Rakoto, eh oui, c’est bien Rakoto, un malgache et quelques survivants ont été coincés sur une île. En explorant l'île, ils découvrent toujours des trucs bizarres. Par exemple, sur un rocher a été écrit des chiffres. A la première impression, les chiffres ressemblent beaucoup à des coordonnées géographiques (longitude, latitude,...).
Avec ces chiffres il y a aussi différentes figures géométriques qui suggèrent des significations. Mais une de ces figures est très remarquable, une suite de 0 et de 1 formant une étoile, confondu avec des dessins d'antenne, d'ordinateurs,... enfin, il y a aussi quelques lettres
Selon eux, la dernière peut indiquer un lieu où ils pourront trouver quelque chose qui leur permettront de survivre ou même de sortir de l'île. En essayant de déchiffrer les figures, quelques unes semblent indiquer des dangers,

Les tâches sont loin d'être faciles pour eux. Heureusement, un de ses coéquipiers avait encore pu garder avec lui son netbook. Pas d'Internet, pas de communication, ... cette machine ne servira à rien. Mais Rakoto, ayant parfois une vision hors du commun a voulu vérifier s'il y a au moins un logiciel ou autre chose qui permettra de manipuler les chiffres. Le courageux, il veut essayer de débusquer ce qui se cache derrière les chiffres du rocher.
A vrai dire, avec le récepteur GPS intégré du netbook il veut essayer de dresser une carte à partir des chiffres écrits sur le rocher et de trouver le chemin tout en évitant les dangers.
Le récepteur GPS fournit juste les coordonnées géographiques du point où le netbook se trouve. Il a aussi trouvé dans le netbook une sorte de logiciel d'apprentissage de l'algorithmique pour les débutants. On ne connaît pas le langage utilisé, mais, celui ci semble être un peu obsolète, pas assez de bibliothèques ni de fonctions, ...

Plusieurs fonctions standards, même basiques doivent être alors réécrites. Rakoto, avec ses idées floues, partage les tâches avec ses collègues. Ces derniers, sans vraiment savoir l'utilité, sont chargés d'écrire plusieurs algorithmes. Tout ce qu'ils savent, c'est que, après, Rakoto va rassembler ces algorithmes dans un programme. Evidemment, ce programme leur aidera à retrouver le point marqué par la figure d'étoile et d'antennes.

Voici juste 3 extraits de ces tâches

Tâche 1 : Le temps

Dans la plupart des cas, espace et temps sont deux choses inséparables. Le langage disponible sur le netbook, dont on ignore encore le nom, ne peut que fournir le nombre de secondes écoulées depuis le lancement du programme. Afin de pouvoir bien travailler avec le temps, les durées, Rakoto doit manipuler les dates et les heures sous d’autres formats. Evidemment, il doit réécrire des fonctions de manipulation des dates et heures.

Voici un extrait de l’algorithme à développer.
Votre algorithme doit alors lire l’heure et les minutes, et affichera l’heure qu’il sera, une minute plus tard. Par exemple, si on a en entrée 21 puis 32, l'algorithme doit répondre : 21 et 33.
Cet algorithme est destiné à prédire l'avenir, et il doit être infaillible !

NB : Pas besoin de vérifier si l’heure est valide ou non.

Validité de l’algorithme : 20 pts
Efficacité : 5 pts

Entrée  : 2 variables représentant
            -l’heure
            -la minute

Sortie   : 2 variables représentant
            -l’heure
            -la minute

Tâche 2 : Une bonne équipe
On pense que vous avez déjà deviné que Rakoto est un bon leader. Mais comme d’habitude, il a des principes que les gens ne comprennent pas. Par exemple, la numérologie ou science des nombres est une des choses qui l’intéressent.

En quelques mots, en numérologie, on essaie de démontrer que tout a été construit à partir des nombres. Et que les nombres régissent la vie humaine.

Le roi Louis XIV, 14ème du nom et déclaré majeur à 14 ans, monta sur le trône le 14 mai 1643 (1+6+4+3 = 14), fut sauvé par Turenne à Blineau en 1652 (1++6+5+2=14), gouverna après Mazarin en 1661 (1+6+6+1=14), signa le traité de Douvres en 1670 (1+6+7+0=14) et mourut en 1715 (1+7+1+5=14) à l'âge de 77 ans (7+7=14).

Rakoto doit construire une équipe pour la recherche de l’endroit secret. Il a une méthode particulière, dans le choix de ses compagnons. Il choisit seulement les personnes qui ont la même chiffre de chance.

Pour chercher le chiffre de chance d’une personne, on procède comme suit : on additionne les chiffres composants la date de naissance de la personne concernée. Avec le nombre obtenu, on refait le même procédé jusqu’à ce qu’on obtienne un nombre composé d’un seul chiffre. C’est le chiffre de chance.

Ecrire un algorithme qui permet de calculer ce chiffre

Entrée  : 3 variables représentant
-le jour
-le mois
-l’année

Sortie   : 1 variable
-le chiffre de chance

Tâche 3 : Il est temps de dessiner la carte

L’outil suivant lui sera nécessaire pour dessiner la carte à partir des coordonnées,…
Ceci n’est qu’un extrait de l’algorithme

Une image est constituée d'un ensemble de points appelés pixels (pixel est une abréviation de Picture Element) Le pixel représente ainsi le plus petit élément constitutif d'une image numérique. L'ensemble de ces pixels est contenu dans un tableau à deux dimensions constituant l'image.

Dans l’exemple ci-dessous chaque case du tableau représente un pixel.
Définition de l’image : 16 x 16 (pixels)

Notons [x,y] les coordonnées d’un pixel situé à la x-ième colonne et à la y-ième ligne.
-L’axe des x est orienté de la gauche vers la droite
-L’axe des y est orienté du haut vers le bas
L’origine est l’élément situé au coin haut gauche du tableau (image).
L’image noir et blanc ci-dessus est codée dans un tableau à deux dimensions contenant des 1 et des 0. Rakoto a choisit de représenter un pixel coloré en noir par 1 et par 0 un pixel en blanc.

0000000000000000
0000000000000000
0011111111100000
0010000000100000
0010000000100000
0010000000100000
0010000000100000
0010000000100000
0011111111100000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

Votre algorithme doit alors prendre en entrée la longueur du côté X (suivant l’axe des x), puis du côté Y (suivant l’axe des y) en pixels d’un rectangle, les coordonnées du centre et générer ensuite la matrice de 0 et de 1 qui constitue l’image. La définition totale de l’image est 256 x 256. L’épaisseur de la ligne est de 1px.

Exemple : La matrice ci-dessus est le résultat de 
                        X=9 ; Y=7 ; [Xc,Yc]=[6,5]

Deux choses sont sûres, on n’entrera pas de données qui peuvent générer un rectangle qui déborde l’espace 256 x 256, les longueurs de chaque côté X et Y sont toujours impaires.
Pour initialiser tous les éléments d’un tableau à 1, par exemple, écrivez juste :
« Initialisation des éléments du tableau <nom du tableau> à 1 »

Entrée  : 4 variables représentant
            -la longueur du côté X
            -la longueur du côté Y
            -Coordonnée suivant x du centre
            -Coordonnée suivant y du centre

Sortie   : Une matrice 256 x 256 contenant de 1 et de 0 représentant l’image

Bon, c’est tout pour aujourd’hui. Rendez-vous à la demi-finale pour la suite de l’histoire.