[1]France IOI Menu [2]Olympiades [3]Entraînement [4]Algorithmique [5]Méthodes [6]Programmation C [7]Programmation Caml [8]Concours [9]Parrainages [10]Clubs informatiques [11]Forums [12]L'association [13]Plan du site Connexion login : ____________ pass : ____________ [14]s'inscrire login News 15/10: [15]Concours France-IOI 14/10: [16]Concours USACO 21/08: [17]3 médailles 15/08: [18]Départ aux IOI 03/07: [19]Equipe de France 2007 Soumissions réussies 11h00: fannou Formes creuses 10h41: fannou Deux rectangles 10h35: fannou Deux codes secrets 10h33: fannou Code secret deux fois 10h07: fannou Zones de couleurs 09h50: mc Tester les alias de ré.. 09h48: mc Tester les alias de ré.. 09h46: mc Affiche le nombre d'en.. 09h42: mc Affiche la somme des r.. 09h41: mc Affiche la somme des N.. 09h40: mc Affiche la somme d'ent.. 09h37: mc Tester les références 2 -> [20]FranceIOI -> [21]Algorithmique -> [22]Concours France-IOI, 2 et 3 juin 2007 -> [23]Jeu de piste - Connectez vous pour pouvoir soumettre vos solutions - Jeu de piste Auteur : Mathias Hiron >> Version imprimable PROBLEME Vous et votre meilleur ami participez à un grand jeu de piste dans la forêt. Le but du jeu est de résoudre E énigmes (numérotées de 1 à E) posées par des organisateurs situés en différents lieux de la forêt, dont on vous fournit les coordonnées GPS. Atteindre les positions des énigmes n'est pas un problème, car vous disposez tous deux d'un ordinateur de poche dernier cri, avec géolocalisation, vous permettant à tout moment de visualiser votre position sur une carte détaillée de la forêt, ainsi que les positions de toutes les énigmes. Toute la difficulté du jeu va donc consister à résoudre les énigmes. Aucun de vous deux n'est très doué pour le genre d'énigmes proposées dans ce jeu. La première énigme est toujours facile à résoudre, mais les autres sont quasiment introuvables sans un indice. Heureusement, une fois que vous avez résolu une énigme donnée, l'organisateur qui vous l'a posée vous donne un gros indice qui vous permet de résoudre facilement l'énigme suivante (par ordre de leur numéro). Pour éviter de perdre du temps à chercher à résoudre les énigmes sans indices, vous décidez donc de les résoudre dans l'ordre de leur numéro. Les énigmes sont cependant placées de manière assez aléatoire dans la forêt, et les parcourir dans l'ordre demande de nombreux allers-retours. [piste1.png] Pour éviter de perdre trop de temps, vous et votre ami décidez de vous séparer, et de vous répartir les énigmes. Vous pouvez par exemple décider de résoudre toutes les énigmes paires, tandis que votre ami résoudra les énigmes impaires. Ainsi, dès que votre ami aura résolu l'énigme numéro 1, et obtenu l'indice pour l'énigme numéro 2, il vous l'enverra par mail via son ordinateur de poche, et vous pourrez alors résoudre cette énigme dès que vous aurez atteint sa position. Vous décidez d'écrire un petit programme pour déterminer, à partir de la description de la carte et des positions des différentes énigmes, la meilleure répartition possible des énigmes entre vous et votre ami, c'est à dire celle qui permet de résoudre l'ensemble des énigmes en un minimum de temps. Vous partez tous les deux de la position de l'énigme 1, et vous pouvez vous déplacer dans l'ensemble du graphe sans autre contrainte que le temps nécessaire pour parcourir chaque chemin. Vous pouvez traverser des énigmes sans les résoudre tout de suite, et pouvez également rester attendre sur une énigme en attendant de recevoir un indice. Le jeu s'arrête lorsque vous résolvez la dernière énigme. On considèrera qu'une fois que vous êtes à la position où se trouve une énigme, et que vous ou votre ami avez résolu l'énigme précédente et obtenu l'indice, résoudre l'énigme suivante ne prend aucun temps. Seule l'énigme 1 peut être résolue sans indice. On vous garantit qu'il est toujours possible de résoudre toutes les énigmes. LIMITES DE TEMPS ET DE MEMOIRE * Temps : 1 s sur une machine à 1Ghz. * Mémoire : 16000 Ko. CONTRAINTES * 1 <= E <= 30, où E est le nombre d'énigmes. * 1 <= C <= 450, où C est le nombre de chemins reliant chacun les emplacements de deux énigmes. * 1 <= L <= 20, où L est le nombre de minutes pour parcourir un chemin. Dans 30% des tests, on a E <= 15. Dans 60% des tests (qui incluent les 30% précédents), on a C <= 50. ENTREE La première ligne de l'entrée contient deux entiers séparés par un espace : le nombre E d'énigmes, et le nombre C de chemins à double sens reliant ces énigmes. Deux énigmes ne peuvent être reliés que par un seul chemin. Chacune des E lignes suivantes décrit un chemin, sous la forme de 3 entiers séparés par des espaces : les numéros des lieux reliés par le chemin, puis le temps nécessaire en minutes pour le parcourir. Les chemins sont donnés dans un ordre quelconque. SORTIE Vous devez afficher un entier sur la sortie : le nombre minimal de minutes nécessaire pour résoudre toutes les énigmes dans l'ordre, en les répartissant au mieux entre vous et votre ami. EXEMPLE(S) D'ENTREE / SORTIE Exemple 1 : en entrée ... 7 10 1 2 4 1 3 3 2 3 3 2 5 4 3 7 3 4 5 5 4 6 4 4 7 5 5 6 3 5 7 2 en sortie ... 15 COMMENTAIRES L'entrée correspond au dessin fourni dans la description du sujet. Voici le parcours le plus rapide pour vous (P1) et votre ami (P2). [piste2.png] Détail du déroulement : Temps Evénement 0 P1 résout l'énigme 1 et part vers l'énigme 2. P2 part également de l'énigme 1, et se dirige vers l'énigme 3. 3 P2 arrive à l'énigme 3 mais ne la résout pas et repart aussitôt vers l'énigme 7. 4 P1 arrive à l'énigme 2 et la résout. Il obtient l'indice pour l'énigme 3 vers laquelle il se dirige. 6 P2 arrive à l'énigme 7 et repart aussitôt vers l'énigme 4. 7 P1 arrive à l'énigme 3, la résout, obtient l'indice de l'énigme 4 et le transmet à P2, puis part vers l'énigme 7. 10 P1 arrive à l'énigme 7 et repart aussitôt vers l'énigme 5. 11 P2 arrive à l'énigme 4 et la résout, puis envoie l'indice de l'énigme 5 à P1, et part vers l'énigme 6. 12 P1 arrive à l'énigme 5, la résout et envoie l'indice de l'énigme 6 à P2, puis repart vers l'énigme 7. 14 P1 arrive à l'énigme 7 et attend l'indice. 15 P2 arrive à l'énigme 6, la résout et envoie l'indice de l'énigme 7 à P1. P1 résout l'énigme 7. Le jeu de piste est terminé. >> Testez votre solution avec vos propres exemples d'entrée >> Puis soumettez votre solution pour la valider >> Retour à l'épreuve _________________________________________________________________ [24]France-IOI References 1. http://www.france-ioi.org/index.php 2. http://www.france-ioi.org/ioi/index.php 3. http://www.france-ioi.org/train/index.php 4. http://www.france-ioi.org/train/algo/index.php 5. http://www.france-ioi.org/train/algo/cours/index.php 6. http://www.france-ioi.org/train/prog/cours_c/ 7. http://www.france-ioi.org/cours_caml/ 8. http://www.france-ioi.org/concours/index.php 9. http://www.france-ioi.org/parrainage/index.php 10. http://www.france-ioi.org/clubs/index.php 11. http://www.france-ioi.org/forum/index.php?method=logout&list=maillistuser&fromlist=maillist&frommethod=showhtmllist 12. http://www.france-ioi.org/asso/index.php 13. http://www.france-ioi.org/plan.php 14. http://www.france-ioi.org/user/index.php 15. http://www.france-ioi.org/news.php 16. http://www.france-ioi.org/news.php 17. http://www.france-ioi.org/news.php 18. http://www.france-ioi.org/news.php 19. http://www.france-ioi.org/news.php 20. http://www.france-ioi.org/index.php 21. http://www.france-ioi.org/train/algo/index.php 22. http://www.france-ioi.org/train/algo/epreuve.php?epreuve=256 23. http://www.france-ioi.org/train/algo/sujet.php?epreuve=256&sujet_id=991 24. http://www.france-ioi.org/asso/contacts.php