Joseph Malaise--Voyageur – Épreuve régionale 2025

Niveau 1 ⋅ Validation weight: 100%

Énoncé

Joseph a obtenu une réponse d'un de ses collègues, Joseph Malaise--Voyageur, qui occupe un poste d'agent du transport maritime dans la cité.

Joseph Malaise--Voyageur lui indique avoir de précieuses informations à lui transmettre, et lui promet de l'aider à condition que Joseph l'aide en retour.

Joseph Malaise--Voyageur est en fait bien embêté. L'un des trains sous-marins est tombé en panne à une station et ne peut plus avancer.

En temps normal, les trains passent toutes les M minutes. Comme le train de Joseph Malaise--Voyageur vient tout juste de tomber en panne, les trains se situent toujours à M minutes d'écart.

Il doit déterminer les stations affectées par le retard. Il a à sa disposition un plan de la ligne de train, ainsi que le temps de voyage en minutes entre chaque station.

Le train en panne est arrêté à la première station. Devant chaque quai, le temps d'arrivée prévu des 2 prochains trains est indiqué.

Aidez Joseph Malaise--Voyageur à trouver la première station pour laquelle le train en panne n'est pas indiqué sur le quai. Si aucune n'existe, affichez "RETARD".

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de stations après celle de Joseph Malaise--Voyageur.
  • Sur la ligne suivante, un entier : M, le nombre de minutes entre chaque train.
  • Sur les lignes suivantes, une liste de N éléments : stations, la liste des stations succédant à celle de Joseph.
    • Une ligne par élément de la liste : une chaine de 10 caractères ou moins.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : temps de voyage, le temps de voyage entre chaque station (en minutes).

Sortie

Afficher, sur une ligne, le nom de la première station qui n'indique pas de retard. Si toutes les stations indiquent le retard, afficher "RETARD" sur une ligne.

Contraintes

  • $1 \le N \le 15$
  • $1 \le M \le 50$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
2
B
C
D
1 3 2
Exemple de sortie
C
Commentaire

Commençons par reconstruire le schéma de la ligne :

Exemple

Ici, chaque train va de gauche à droite. Pour décrire le temps affiché à chaque quai, on utilise la terminologie suivante :

  • n min lorsque le train n'est pas en retard et son arrivée à quai est prévue dans n minutes;
  • 0 min lorsque le train est sur le quai;
  • ++ pour le train en panne.

Le train en panne se situe sur le quai de la première station, où se situe Joseph Malaise--Voyageur. On considère donc qu'il est affiché ++ et ++ sur le quai.

Calculons le temps d'arrivée des trains pour chaque quai : $M$ valant $2$ dans l'entrée, chaque train se situe actuellement à $2$ minutes d'écart.

Le train à $2$ minutes d'écart de celui à la station de Joseph se trouve sur la voie entre la station $B$ et la station $C$. Plus précisément à $2$ minutes de la station $C$.

À la station $B$, le train le plus proche se situe donc sur le quai de la station $A$. Il s'agit du train en panne. Il est donc affiché sur le quai ++ et ++.

Le prochain train, situé à $4$ minutes du train de la station de Joseph, se trouve sur le quai de la station $C$. C'est le train le plus proche de la station $C$.

Le second plus proche est le train sur la voie entre $B$ et $C$, il est donc affiché 0 min et 2 min sur le quai.

La station $C$ étant la première station où l'on n'affiche pas ++, c'est donc le résultat attendu.

Exemple d'entrée
2
2
B
C
2 1
Exemple de sortie
RETARD
Commentaire

Voici le plan de la ligne :

Exemple

Calculons la position des trains sur la ligne, les trains partant toutes les 3 minutes.

Voici les temps affichés sur chaque quai :

  • 0 min et ++ pour la station B;
  • 1 min et ++ pour la station C.

Il n'y a aucune station qui n'affiche pas le retard, on écrit donc RETARD sur la sortie standard.