Contest L3 info / L3 BIM 2006 : Black Box
Modalités.
Durée de la compétition. Vous devez nous envoyer les sources de vos programmes au plus tard le lundi 25 septembre à 12h00.
Les sources. Ecrites en C ANSI (pas de C++), nous devons pouvoir les compiler facilement sous Linux avec gcc.
L'évaluation. Nous lancerons tous les programmes sur un jeu de problèmes, avec un temps limite de 300 secondes pour chaque problème. Le classement se fera en fonction du nombre de problèmes résolus, du nombre de problèmes partiellement résolus, et du temps de calcul.
Résultats du contest.
The winners : équipe 6
Amandine R.
Roland A. R.
Grégory G.
Fabien R.
Les seconds : équipe 3
Rémy J.
Rémy P.
Youcef S.
Les troisièmes : équipe 5
Benjamin D.
Guillaume G.
Gilles M.
Driss S.
Ont aussi concourus
Equipe 10, équipe 7
Ont participé
Equipe 1, équipe 9, équipe 11,
équipe 13
N'ont pas participé
Equipe 2,
équipe 4,
équipe 8,
équipe 12.
Karim Nouioua s'est occupé de presque tout, encore merci !
Détails des résultats.
Le problème.
Etant donnée une grille carrée sur laquelle sont positionnés des atomes, déterminer les positions de ces atomes à partir d'informations obtenues en lançant des rayons laser dans la boite.
La taille de la grille (de dimension 2) est connue, ainsi que le nombre d'atomes.
Deux atomes ne peuvent pas occuper la même position dans la grille.
Les règles de propagation des rayons dans la grille sont les suivantes :
- les rayons se propagent dans les directions EST, OUEST, NORD et SUD, en respectant les règles qui suivent, et ce tant que le rayon est dans la grille et n'a pas été absorbé,
- en l'absence d'obstacles (voir les situations décrites ci-dessous) un rayon se propage droit devant lui,
- s'il arrive sur une case occupée par un atome, il est absorbé (c'est la cas des rayone qui entrent en 3, 27 ou 21),
- sinon, s'il arrive sur une case (vide) dont les cases voisines à droite et à gauche sont occupées par des atomes, il est réfléchi (rayon entrant en 10),
- sinon, s'il arrive sur une case dont la case voisine de droite (resp. de gauche) est occupée par un atome, il est dévié vers la gauche (resp. vers la droite) (rayon entrant en 0),
- au fur et à mesure de sa propagation un rayon peut rencontrer plusieurs de ces situations, et par exemple subir plusieurs déviations avant d'être absorbé (rayon 21).
Attention ! Il se peut que des erreurs se glissent dans les résultats, dues à des problèmes pratiques de relevés de mesures.
Il peut donc arriver qu'aucun placement des atomes sur la grille ne produise les entrées/sorties demandées.
Dans ce cas le problème n'a pas de solution.
Remarque.
Pour éviter les effets indésirables et simplifier le traitement des bords, la grille est entourée d'une frontière inhabitée (premières et dernières lignes et colonnes, en grisé sur la figure).
Les données et les résultats que vous devez produire.
Vous respecterez strictement le formalisme demandé, afin que nous puissions facilement tester vos programmes.
Fichiers de données. Ce sont des fichiers texte. Ils respectent un format particulier. Sous Linux vous pourrez utiliser le programme de génération genere pour produire des instances aléatoirement (essayez d'abord ./genere -help).
Ces fichiers ne contiennent que des valeurs numériques entières.
La première valeur est la taille de la grille (avec la frontière), suivent le nombre d'atomes, puis le nombre de rayons.
Le fichier contient ensuite, pour chaque rayon, sa porte d'entrèe et sa porte de sortie (-1 si le rayon a été absorbé).
Le fichier décrivant le problème ci-dessus serait le suivant :
8
5
6
0 29
3 -1
10 10
7 16
21 -1
27 -1
Résultat du programme. Votre programme devra produire des résultats sous la forme suivante, sous peine de ne pas pouvoir être évalué.
Si vous trouvez une solution, complète ou partielle (i.e. qui satisfait certains des lancers de rayons du problème, mais pas tous), alors afficher uniquement des valeurs numériques : la taille de la grille, le nombre d'atomes, pour chaque atome ses coordonnées dans la grille (la première ligne et la première colonne ont le numéro 0).
Avec la grille ci-dessus ça donnerait :
8
5
1 3
1 4
3 1
4 6
3 3
Si votre programme démontre qu'il n'y a pas de solution, alors afficher NO.
Sinon n'affichez rien.
