I. 157. Nos lecteurs réguliers se souviennent certainement de notre détective célèbre Touteouie. Pour ses dernières investigations (I. 134.), il a demandé notre aide. Malheureusement, les ,,mauvais garçons'' se sont rendus compte que l’étau se resserre autour d’eux et ils envoient maintenant leurs informations en message codé. Touteouie voudrait les pincer à tout prix mais pour cela il devrait pouvoir décoder les messages et aussi être capable d’en écrire lui-même. Les messages codés ne contiennent que des nombres séparés par des points virgules. Le détective a appris que les brigands signaient toujours leurs messages, par exemple la suite de nombres

119; 25; 125; 69; 80; 118; 67; 147; 43; 21; 109; 29; 88; 128; 130; 72; 58; 156;

correspond à la signature de Hack Elmer. Touteouie a aussi remarqué que la suite de nombres n’est pas constante, par exemple la suite

112; 32; 36; 158; 63; 135; 97; 117; 44; 20; 51; 87; 58; 158; 49; 153; 83; 131;

est aussi la signature codée de Hack Elmer. Notre tache est la suivante: trouver la méthode d’encodage des messages puis écrire un programme qui aidera le détective dans la lecture des messages codés et dans l’écriture de nouveaux messages. Trois paramètres doivent suivre le nom du programme: le premier paramètre est obligatoirement le mot ,,en'' ou ,,de'', en signifiant l’encodage, de le décodage. Ensuite, le nom du fichier en entrée ; le dernier paramètre étant le nom du fichier de message écrit. Par exemple: i157 de secret.txt resolu.txt décode le fichier secret et place le résultat dans fichier resolu.

Envoyer le code source du programme (i157.pas, i157.cpp, ).

(10 points)

I. 158. Des messagers partent de la constellation centrale de la république galactique pour apporter le nouveau drapeau de la république dans chaque constellation de la galaxie. Les dirigeants de la république pensent que la manière la plus rapide est d’envoyer un messager dans chaque constellation dans une navette spatiale. Dans ce cas, c’est dans la constellation la plus éloignée que le drapeau arrivera en dernier.

Ils se sont rendu compte ensuite que les messagers arrivant dans les constellations pouvaient repartir vers d’autres constellations. Il serait même possible que plusieurs messagers partent vers une constellation et, après avoir transmis le drapeau, chacun d’eux continue son chemin vers une autre constellation. Pour ceci, ils disposent dans chaque constellation de suffisamment de navettes qui avancent toutes à la même vitesse et peuvent transporter un nombre quelconque de messagers.

Les dirigeants de la république ont décidé d’envoyer les messagers de cette manière. Leur but est que, avant ou au moment de l’arrivée de la navette directe envoyée vers la constellation, les drapeaux arrivent dans toutes les autres constellations. Donc, l’arrivée du dernier drapeau ne peut pas être plus tardive que dans le cas où ils auraient envoyé une navette vers chaque constellation.

Calculer la diminution maximum possible des chemins parcourus par les navettes par rapport à la première idée d’envoi direct d’une navette vers chaque constellation.

Les données des systèmes d’étoiles sont enregistrées dans un fichier texte sous forme de 3 coordonnées orthogonales. Chaque ligne du fichier contient les coordonnées réelles X, Y, Z   d’une constellation séparées par un caractère d’espacement. La première ligne contient les coordonnées de la constellation centrale. Le programme doit lire à partir de la ligne de commande le nom du fichier en entrée et doit écrire sur la sortie standard tous les trajets des navettes directes, tous les trajets des navettes parcourant les chemins les plus courts possibles ainsi que la différence entre les deux.

Envoyer le code source du programme (i158.pas, i158. cpp, ) et la documentation brève de la solution (i158.txt, i158.pdf, ).

(10 points)

I. 159. Une scierie vend des poutres de différentes tailles sur commande. Les clients peuvent commander des poutres de longueurs fixes mais de coupe selon leurs besoins. La scierie reçoit des troncs d’arbre de diamètres différents et en découpe les formes nécessaires. A cause de la technologie de fabrication en place, à partir d’un tronc d’arbre on découpe des poutres de même taille et parallèles les unes par rapport aux autres. Une découpe possible est illustrée par la figure   ci-dessous.

Créer un tableau Excel qui nous aidera à choisir, à partir de trois tailles de découpes, celle où le produit peut être découpé avec le moins de perte possible. Le classeur doit contenir deux feuilles de calculs; dans la première feuille, on donne les dimensions des trois découpes possibles: par exemple 10 cm×20 cm; 15 cm×15 cm; 12 cm×17 cm, ainsi que le diamètre du tronc d’arbre (par exemple 87 cm). Trouver la découpe la plus avantageuse pour le diamètre donné. Le résultat doit s’afficher dans la même feuille de calcul. L’autre feuille de calcul doit contenir les calculs nécessaires.

A côté de la solution correcte, la présentation et la convivialité (par exemple protection des cellules) seront aussi prises en compte.

(En cas de protection de cellules, il n’est pas nécessaire de donner le mot de passe.)

Envoyer le classeur contenant la solution. (i159.xls, ).

(10 points)

S. 26. Les employés de l’Institut National de Recherche de Trésors (INRT) utilisent les derniers résultats scientifiques et d’anciennes cartes de trésors pour remonter à la surface des objets de valeurs, enfouis sous terre il y a longtemps.

La longue expérience de l’institut montre qu’une grande partie des trésors est enterrée dans des montagnes calcaires dont les rochers durs enferment de nombreuses grottes. Ces grottes sont constituées d’un certain nombre de cavités de tailles différentes pouvant parfois s’encastrer l’une dans l’autre et qui peuvent être considérées comme des cavités sphériques. Au cours des forages, en arrivant dans une grotte, le forage peut être poursuivi à partir d’un point quelconque de la grotte; la distance de forage peut ainsi être diminuée.

Ecrire un programme qui déterminera, en connaissant la structure du sol et en utilisant les cavités, la distance de forage optimale et le point de départ (à la surface) du forage.

Le programme doit lire à partir de l’entrée standard la position du trésor et l’emplacement des cavités. La première ligne de l’entrée contient le nombre N (0N1000)  des cavités et l’altitude Y_s du sol au-dessus du niveau de la mer. Le sol peut être considéré comme un plan horizontal. La deuxième ligne contient les coordonnées X_t, Y_t, Z_t  du trésor, les N  lignes suivantes décrivent les cavités souterraines sous forme de X_i, Y_i, Z_i, R_i  où X_i, Y_i, Z_i  sont les coordonnées du centre de la i-ème cavité, R_i  le rayon de la cavité. Nous pouvons supposer que chaque cavité se trouve entièrement sous terre.

Le programme doit écrire le résultat sur la sortie standard. La seule ligne de celui-ci doit contenir quatre nombres décimaux comportant au moins deux chiffres après la virgule: les coordonnées X, Y, Z  du point de départ du forage et la distance minimum L  du forage.

Envoyer le code source du programme (S26.pas, S26.cpp, ).

(10 points)