Ceintures

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.


Source : http://www.france-ioi.org/