Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]
Deux moines ont décidé de vivre en ermites dans la montagne, loin de toute forme de civilisation. Leur voeu d'isolement est très strict : ils doivent faire tout leur possible pour ne rencontrer aucun autre être humain et s'isoler y compris l'un de l'autre.

Ces deux moines se partagent deux petits chalets, l'un en haut de la montagne, l'autre un peu plus bas. Pour éviter l'ennui, ils se sont mis d'accord pour s'échanger leur chalet une fois par mois. Le premier jour de chaque mois, ils partent chacun de leur côté exactement à la même heure et empruntent les petits sentiers de la montagne, pour se rendre à l'autre chalet. Ils doivent cependant s'assurer de ne pas se rencontrer et de rester dehors le moins longtemps possible, pour réduire les risques de tomber sur un éventuel randonneur.

Heureusement pour eux, de nombreux sentiers parcourent la montagne, ce qui leur offre de nombreuses manières de passer d'un chalet à l'autre. Chaque sentier relie deux croisements où peuvent se rejoindre plusieurs autres sentiers. Deux croisements reliés par un sentier ont toujours une altitude différente et chaque sentier ne fait que monter, ou que descendre entre ces croisements, suivant la direction dans laquelle on l'emprunte.

Les moines doivent consacrer un maximum d'énergie à la prière et souhaitent donc économiser leurs forces au maximum. Le moine qui descend ne doit ainsi jamais emprunter un sentier qui le force à monter et celui qui rejoint le sommet ne doit jamais redescendre pendant son trajet, car il devrait alors remonter d'autant ensuite.

Pendant leur parcours, les deux moines avancent à une vitesse toujours identique, d'exactement un mètre par seconde. Ils ont la possibilité de s'arrêter pour prier, mais le font toujours exactement au début d'une seconde et repartent au début d'une autre seconde. Leur temps d'arrêt doit être un multiple de 10 secondes, le temps de réciter un nombre entier de prières (chaque prière dure exactement 10 secondes).

Les sentiers ont tous une longueur multiple de 10 mètres. Un moine commence à marcher le long d'un sentier au début d'une seconde et atteint son autre extrémité exactement à la fin d'une seconde. Pour ne pas se croiser, les moines ne doivent donc jamais se trouver, au début d'une seconde, sur le même sentier ou à la même intersection.

Remarque : lorsqu'un moine se trouve exactement sur un croisement dont part un sentier, on ne considère pas qu'il se trouve sur ce sentier.

Vous devez écrire un programme qui détermine le temps total minimum nécessaire aux deux moines pour échanger leur chalet sans jamais se croiser. Le temps total est la somme du temps pris par chacun des moines pour son trajet, temps d'arrêts compris.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 16 000 ko.

Contraintes

  • 1 <= D <= 10, où D est le nombre de sentiers qui se rejoignent à un croisement donné.
  • 3 <= C <= 10000, où C est le nombre de croisements.
  • 2 <= S <= 20000, où S est le nombre de sentiers.
  • 10 <= L <= 1000, où L est la longueur d'un sentier en mètres. L est multiple de 10.
  • 0 <= A <= 1000, où A est l'altitude relative d'un croisement par rapport au chalet du bas, en mètres.

De plus, dans 50% des jeux de tests :

  • 3 <= C <= 1000
  • 1 <= S <= 2000

Entrée

La première ligne de l'entrée contient deux entiers séparés par un espace : le nombre C de croisements et le nombre S de sentiers. Les croisements sont identifiés par des entiers de 1 à C et les sentiers par des entiers de 1 à S.

La deuxième ligne de l'entrée contient deux entiers séparés par un espace : l'identifiant du croisement correspondant au chalet du bas, suivi de celui du chalet du sommet.

Les C lignes suivantes contiennent chacune un entier : l'altitude d'un croisement. Les altitudes sont données dans l'ordre des identifiants des croisements. Ainsi, la 3ème ligne de l'entrée indique l'altitude du croisement d'identifiant 1.

Les S lignes suivantes décrivent les sentiers. Chaque ligne contient 3 entiers séparés par des espaces : les numéros des deux croisements reliés par le sentier, puis sa longueur L en mètres.

Attention : les croisements ne sont pas nécessairement fournis dans l'ordre de leur altitude. Le croisement K peut ainsi avoir une altitude plus élevée que le croisement K + 1. Les extrémités d'un sentier peuvent également être données dans l'ordre inverse de leurs altitudes.

Sortie

Vous devez écrire une ligne sur la sortie, contenant un entier : le temps total, en secondes, nécessaire aux deux moines pour échanger leur position.

Exemples

Exemple 1

entrée :

4 4
1 4
0
9
22
45
1 2 200
2 3 50
2 3 80
3 4 100

sortie :

760

Exemple 2

entrée :

5 7
1 5
0
3
7
9
15
1 2 30
1 3 80
2 3 40
2 4 40
3 4 30
3 5 40
4 5 50

sortie :

230

Commentaires

La figure suivante illustre les deux exemples. Le chalet du sommet se trouve en haut de la figure. Les chiffres rouges correspondent aux identifiants des croisements.


* illustration non contractuelle

Dans le premier exemple, le moine qui part du bas commence au croisement numéro 1. Il parcourt alors 200m sur le sentier 1 et arrive au temps 200 au croisement 2. Il parcourt ensuite 50m sur le sentier 2, vers le croisement 3, qu'il atteint au temps 250. Il emprunte finalement le sentier 4, qui va vers le chalet du sommet et parcourt 100m, pour l'atteindre au temps 350, soit après un trajet total de 5mn 40 secondes.

Le moine qui descend part de son chalet exactement au moment du départ du premier moine. Il parcourt tout d'abord 100m sur le sentier 4, pour arriver au croisement 3 au temps 100. Il emprunte alors le sentier 3, et parcourt 80m, mais fait une pause de 30 secondes pendant ce trajet, pour arriver au croisement 2 au temps 210, soit 10 secondes après le passage du premier moine, ce qui lui permet de ne pas le rencontrer. Il emprunte finalement le sentier 1 et atteint le chalet du bas au temps 410.

Le temps total de trajet des deux moines est donc de 350 + 410 = 760 secondes. Il leur est impossible d'échanger leur position en moins de temps.

Dans le deuxième exemple, le moine qui monte emprunte les sentiers 1, 3 et 6, pour atteindre le sommet après 110 secondes de marche sans pause. L'autre moine emprunte les sentiers 6, puis 2, et atteint le chalet du bas après 120 secondes de marche sans pause. Le temps total est donc de 230 secondes, ce qui est le plus petit temps possible.

Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.

Correction en cours de chargement…