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]
C'est la semaine de la mode, et vous essayez les dernières ceintures design de Paris. Malheureusement, aucune des ceintures n'est à votre taille, ce qui indique clairement une chose : vous avez besoin de faire plus d'exercice.

Vous décidez que le meilleur moment pour faire de l'exercice est lors de chacun de vos trajets de retour à la maison en tramway. Le tramway va en ligne droite de l'école à la maison, et la ligne contient plusieurs arrêts. Vous pouvez faire de l'exercice en descendant du tramway à un arrêt, marchant vers un autre stop plus loin le long de la ligne, puis remontant dans le prochain tramway qui passe par là. Vous pouvez faire ceci autant de fois que vous souhaitez (utiliser le tramway, marcher, utiliser le tramway, et ainsi de suite). Vous pouvez choisir de commencer le trajet en marchant, et vous pouvez décider de descendre d'un tramway à un arrêt, et finir le trajet à pied.

Les tramways passent toutes les T minutes, et le premier tramway quitte votre école précisément quand vous commencez votre trajet. Les tramways se déplacent à vitesse fixe, et vous marchez également à une vitesse fixe, plus lente. Vous ne pouvez marcher que vers chez vous (vous ne pouvez pas retourner vers l'école ni tourner en rond). Si vous marchez de l'arrêt A à l'arrêt B et attrapez le tramway suivant, vous attendez simplement à l'arrêt B et écoutez votre lecteur de mp3 jusqu'à-ce que le prochain tramway passe. Si vous arrivez à l'arrêt B précisément au moment où un tramway passe, vous pouvez monter à bord.

Après avoir parcouru quelques magazines de santé, vous décidez que vous avez besoin de marcher au moins K mètres lors de vorte trajet. Votre objectif est de trouver le temps de trajet le plus petit possible, allant du début à la fin et qui respecte les conditions décrites plus haut.

Exemple

Considérez la ligne de tramway illustrée ci-dessous. Elle commence par l'école du côté gauche, après laquelle se trouvent S=6 arrêts. Les distances entre les arrêts consécutifs sont indiquées sur le diagramme, et votre maison se trouve au tout dernier arrêt.

Supposez que la gestion du tramway soit très performante et que les tramway passent toutes les 30 secondes, i.e., toutes les T=30 000 millisecondes. Les tramways prennent Mt=1 millisecondes pour se déplacer d'un mètre et il ne vous faut que Mw=100 millisecondes pour marcher un mètre. Votre régime minceur vous impose de marcher au moins K=870 mètres durant votre trajet.

Une stratégie optimale pour rentrer chez vous est la suivante :

ActionArrêtsDistanceTemps
Utiliser le tramwayEcole--1450m450ms
Marcher1--2300m30 000ms
Attendre le tramway2 300ms
Utiliser le tramway2--3450m450ms
Marcher3--5600m 60 000ms
Attendre le tramway5 600ms
Utiliser le tramway5--6450m450ms
Total   92 250ms

Votre distance totale de marche selon ce plan est de 900m, ce qui est suffisant car c'est plus que les K=870m requis. Le temps de trajet total est de 92 250 millisecondes.

Limites de temps et de mémoire (Python)

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

Contraintes

Tous les temps ci-dessous sont mesurés en millisecondes et toutes les distances sont mesurées en mètres.

  • 30 000 <= T <= 1 000 000, où T est le temps entre chaque tramway et le suivant;
  • 1 <= Mt < Mw <= 100, où Mt est le temps nécessaire à un tramway pour avancer d'un mètre et Mw est le temps dont vous avez besoin pour marcher d'un mètre;
  • 1 <= K <= 10 000, où K est la distance minimale que vous devez marcher;
  • 1 <= S <= 100, où S est le nombre total d'arrêts de tramway (sans compter l'école où votre trajet commence);
  • Il n'y a jamais deux arrêts séparés de plus de 1 000 mètres;
  • Le dernier arrêt est au moins à K mètres de l'école (i.e., il est possible de marcher assez pour obtenir l'exercice dont vous avez besoin).

De plus, 30% des points seront attribués à des tests dans lesquels la distance de marche minimale satisfait K <= 2 000.

Entrée

Votre programme doit lire sur l'entrée standard. La première ligne contiendra un simple entier T, qui donne le temps entre chaque tramway et le suivant. La deuxième ligne contiendra les deux entiers Mt et Mw séparés par un espace, donnant le temps nécessaire à un tramway pour se déplacer d'un mètre, et le temps qu'il vous faut pour marcher un mètre. La troisième ligne contiendra un simple entier K, donnant la distance minimale que vous avez besoin de marcher.

La quatrième ligne de l'entrée contiendra l'entier S, donnant le nombre total d'arrêts de tramway (à l'exception de l'école où le trajet commence). Les S lignes suivantes donnent les positions des arrêts individuels dans l'ordre, de l'école à votre maison. La ième de ces lignes contiendra l'entier Di, donnant la distance de l'école au ième arrêt. Votre maison est au dernier de ces arrêts.

Une fois de plus, tous les temps sont mesurés en millisecondes et toutes les distances sont mesurées en mètres.

Sortie

Votre programme doit écrire une simple ligne sur la sortie standard, contenant un entier : la durée totale de trajet la plus courte possible, mesurée en millisecondes.

Exemple

entrée :

30000
1 100
870
6
450
750
1200
1740
1800
2250

sortie :

92250

Commentaires

Calcul du score

Le score pour chaque test d'entrée sera de 100% si la bonne réponse est fournie, et 0% sinon.

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…