Olympiade d'Informatique de Madagascar

Entrainement > Demi-finale 2008

Durée : 2h30

Pour toutes les tâches bien respecter l’ordre de saisie des variables d’entrée.
Pendant l’évaluation votre programme sera testé avec de différents variables d’entrée.

Tâche 1 : Le portail

Grâce aux outils qu’ils ont développés, Rakoto et son équipe ont pu trouver l’endroit marqué sur le rocher par des antennes et des étoiles. Ils sont devant un bâtiment entourés d’éoliennes, de plaques solaires et d’antennes avec un portail blindé et anti-explosion. Ils sont maintenant sûrs que s’ils arrivent à ouvrir ce portail ils peuvent accéder à des moyens de communication.

L’ouverture du portail se fait par saisie d’un code de 3 chiffres. Vous voyez que le système de codage n’est pas assez compliqué mais la saisie de 5 codes erronés entraîne le blocage du système.
Le code est formé de trois (3) chiffres (1 à 9, pas de 0) différents donc 504 possibilités. Pour une meilleure compréhension, voici quelques exemples de codes valides (syntaxiquement) et non valides.

268, 319, 791 : valides
203, 133, 606 : non valides

Sur le portail, il y a déjà deux indices :
- un code valide (suivant une certaine règle ou formule) : 913
- la clé de codage : 24
Ces derniers ne permettent pas d’ouvrir le portail mais par contre, permettent de générer d’autres codes valides si on arrive à les analyser.

Exemple :
Code : 364
Clé de codage : 22

Chiffre 1 (centaine) : 3 opérateur 1 : + (addition)
Chiffre 2 (dizaine) : 6 opérateurs 2 : - (soustraction)
Chiffre 3 (unité) : 4 opérateur 3 : * (multiplication)

La logique entre les chiffres et les opérateurs peut être considérée comme suit :

Les opérateurs <operateur m> et <operateur n> peuvent être identiques.
Par contre Chiffre i ≠ Chiffre j ≠ Chiffre k

i,j,k,m,n étant des indices variant de 1 à 3

A vous de chercher les opérateurs entre les chiffres,
(3 + 6) - 4 =5
(3 - 6) * 4 =-12
(4 - 6) * 3 =-6
…
(6 * 3) + 4 =22 (clé de codage)

Dans notre exemple, on trouve que pour un code valide
(dizaine * centaine)+unité=22

Il suffit de générer des codes suivant cette règle.
2 * 7 + 8 =22
…
7 * 3 + 1 =22

Voici alors des codes valides : 278, 728, 731, 371 ...

Entrée :
-l’unité : int
-la dizaine : int
-la centaine : int
-clé de codage : int

NB : Les trois chiffres formant le code (l’unité, la dizaine, la centaine) doivent être saisis séparément.
Par exemple, si le code est 364 et la clé de codage 22. L’utilisateur doit alors :

-saisir 3 et appuyer sur la touche Entrée
-saisir 6 et appuyer sur la touche Entrée
-saisir 4 et appuyer sur la touche Entrée
-saisir 22 et appuyer sur la touche Entrée

Sortie :
Le programme doit afficher à l’écran :
-8 autres codes de 3 chiffres valides

Votre programme doit marcher avec le code 913 et la clé 24 mais doit aussi marcher avec d’autres codes et clés. On a encore besoin du programme pour les autres portes.

Exemple de fonctionnement du programme.

Indication :
Pour chaque permutation possible des 3 chiffres, essayer d’utiliser toutes les combinaisons* d’opérateurs possibles, évaluer l’expression obtenue.

* : Le terme « combinaisons » n’a pas le même sens que combinaisons en dénombrement.

Tâche 2 : Le temps

Ici on ne fait que reprendre la tâche de l’épreuve éliminatoire.

Votre programme doit alors lire l’heure et les minutes séparément dans deux (2) variables de type entier, 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.

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

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


Exemple de fonctionnement du programme.

Tâche 3 : Totalogramme

Un totalogramme est une chaîne dont les mots commencent et se terminent par la même lettre (sans distinction entre majuscule et minuscule).
Votre programme doit prendre en entrée une chaîne et afficher si c’est un totalogramme ou non.
Pour vous faciliter la tâche, on suppose que la chaîne ne comporte pas de caractères accentués, ni d’apostrophes, ni de chiffres et la longueur maximale est de 60 caractères.

Exemple de fonctionnement du programme.

Tâche 4 : Algorithme de tri

La plupart des algorithmes de tri sont fondés sur des comparaisons successives entre les données pour déterminer la permutation correspondant à l’ordre croissant des données. Nous appelons tri comparatif un tel tri. La complexité de l’algorithme a alors le même ordre de grandeur que le nombre de comparaisons entre les données faites par l’algorithme. Signalons néanmoins qu’il existe aussi des algorithmes de tris non comparatifs comme le tri baquet ou
le tri par paquets.

Une forme dégénérée du tri baquet suit le principe ci-dessous.
Supposons qu’il s’agisse de trier des entiers compris entre 0 et N ; on utilise un tableau supplémentaire T (autre que celui qui contient éventuellement les données) indicé de 0 à N ; la case d’indice p de T contiendra après l’algorithme le nombre de fois que l’entier p figure dans la liste des entiers.

On initialise à 0 toutes les cases du tableau T; on considère successivement tous les entiers de la liste à trier ; si l’entier considéré vaut p, on incrémente T[p] de 1; après avoir traité toutes les données, il suffit de relire le tableau T en partant de l’indice 0 pour connaître la liste triée (si par exemple T[0] vaut 1, T[1] et T[2] valent 0, T[3] vaut 2 et T[4] vaut 1, la liste triée commence par 0, 3, 3, 4). Dans ce tri, on ne compare jamais les données entre elles.

Votre programme doit :
-lire le nombre de données à trier
-lire et insérer dans un tableau les données à trier
-trier les éléments du tableau avec l’algorithme décrit précédemment (ordre croissant)
-afficher à l’écran les données non triées puis les données triées

Entrée :
-Nombre de données à trier : entier
-Données à trier : tableau contenant des entiers

Sortie :
-Données triées : tableau contenant des entiers

Le nombre de données à trier est toujours inférieur à 1000.
Les données à trier sont des entiers compris entre 0 et 100 (0 et 100 inclus)