I. 175. Soient donnés N  intervalles sur la droite des nombres. Déterminer les intervalles de la droites des nombres contenus par un nombre impair d’intervalles parmi les intervalles donnés. Ne pas tenir compte des extrémités des intervalles. La solution doit comporter un minimum d’intervalles, donc les intervalles doivent être disjoints et les intervalles voisins doivent être concaténés.

Le programme doit lire la description des intervalles à partir d’un fichier et écrire le résultat dans un fichier. Les noms de ces fichiers sont transmis par les paramètres de la ligne de commande (par exemple i175 en.txt so.txt). La première ligne du fichier en entrée contient le nombre d’intervalles N (0N7000) les N  lignes suivantes contiennent deux nombres entiers séparés par un caractère d’espacement, les extrémités d’un intervalle, X  le début et Y  la fin (). La première ligne du fichier de sortie doit contenir le nombre d’intervalles M, chacune des M  lignes suivantes contient la description d’un intervalle au même format que le fichier en entrée.

Envoyer le code source du programme (i175.pas, i175.cpp, ...), ainsi que sa documentation brève (i175.txt, i175.pdf, ...) qui contient la description de la solution et le nom de l’environnement où le code source peut être compilé.

(10 points)

I. 176. L’exercice de géométrie suivant a été proposé aux Olympiades de 1988:

Soient donnés dans le plan deux cercles concentriques, de rayons différents. Soit O  leur centre commun. Soit P  un point fixe du plus petit cercle, soit B  un point parcourant le périmètre du plus grand cercle. Soit C  l’autre point d’intersection de la droite BP  avec le plus grand cercle. Soit A  l’autre point d’intersection de la droite l  perpendiculaire à BP  passant par P-ben avec le plus petit cercle (si  l  est la tangente du cercle en P, soit A=P). Déterminer le lieu géométrique du milieu du segment AB.

Résoudre le problème à l’aide du logiciel gratuit GeoGebra (téléchargeable sur Internet). Dans la solution, utiliser les notations de l’énoncé. Créer une animation d’au moins 20 images de taille 400×400 pixels qui illustre la position du point de milieu quand le point B  parcourt le périmètre du plus grand cercle.

Envoyer le fichier GeoGebra i176.ggb illustrant la recherche du lieu géométrique, ainsi que le GIF animé i176.gif.

(10 points)

I. 177. Illustrer la division à l’écrit des nombres en système à base 2.

Créer un tableau qui affichera – après avoir saisi à un emplacement déterminé de sa première ligne deux nombre binaires à cinq chiffres au plus, en écrivant un chiffre par cellule – le déroulement de la division des deux nombres, le quotient des deux nombres et le reste de la division.

Envoyer le classeur (i177.xls, i177.ods, ...) ainsi qu’une documentation brève (i177.txt, i177.pdf, ...) qui contient le nom du tableur utilisé, sa version et la description brève de la solution.

(10 points)

S. 32. Dans un parc national, on peut atteindre tous les points de visite importants à vélo. Mais certaines pistes cyclables se sont détériorées suite aux intempéris d’hiver. On a répertorié toutes les pistes et déterminé leur facteurs de priorité de rénovation, c’est à dire l’importance de leur rénovation.

La direction a décidé que les travaux les plus importants doivent être terminés avant la grande saison d’été tout en assurant une possibilité d’accès à vélo à tous les points de visite importants. On sait qu’il est possible de rénover un nombre quelconque de sections en même temps et la rénovation de chaque section nécessite toute la période de printemps.

Ecrire un programme qui déterminera le nombre maximal de sections de pistes cyclables pouvant être effectuées au printemps et, en se basant sur ce résultat, la somme maximale possible de leurs facteurs de priorité de rénovation.

Le programme doit lire la description des pistes à partir d’un fichier et il doit ensuite écrire le résultat dans un fichier de sortie. Les noms de ces fichiers sont transmis par les paramètres de la ligne de commande (par exemple s32 en.txt so.txt).

La première ligne du fichier en entrée doit contenir le nombre de points de visite N (100 au plus) et le nombre de pistes les reliant M (500 au plus) séparés par un caractère d’espacement. Les objets à visiter seront identifiés par les nombres . Les M  lignes suivantes doivent contenir trois nombres entiers positifs, séparés par un caractère d’espacement, au format A B F : les numéros de deux objets à visiter A, B  et le facteurs de priorité de rénovation F>0 de la piste les reliant dans les deux sens (un entier entre 1 et 1000). Si la piste ne doit pas être rénovée, prendre la valeur F=0.

La sortie est un seul nombre: la somme maximale possible des facteurs de priorité de rénovation des pistes sélectionnées.

Envoyer le code source du programme (s32.pas, s32.cpp, ...), ainsi que sa documentation brève (s32.txt, s32.pdf, ...) qui contient la description de la solution et le nom de l’environnement où le code source peut être compilé.

(10 points)