Passe Styx – Épreuve régionale 2021

Niveau 2

Énoncé

Joseph Marchand est invité à prendre l'apéritif chez son ami Hadès. Joseph meurt d'envie de se rendre chez son ami, mais ne peut pas se permettre de dépenser toutes ses drachmes. Il espère donc pouvoir faire des économies sur le voyage notamment sur le coût de la traversée du Styx.

Charon le passeur est le seul à pouvoir assurer le passage du fleuve et son prix est fixé en fonction de l'horaire de la journée. Joseph se procure donc une tablette répertoriant le coût de la traversée selon l'horaire. Par conséquent l'indication 10 15 20 indique que de 10 heures à 15 heures exclu, il faut payer 20 drachmes. Les horaires sont compris entre 0 et 24, et Charon peut ne pas être disponible à certaines heures.

Le rendez-vous fixé par Hadès est à 18h, chaque heure d'avance oblige Joseph à acheter une bouteille d'hydromel d'un coût de 2 drachmes pour passer le temps alors que chaque heure de retard lui coûte une tournée d'ambroisie à 4 drachmes pour se faire pardonner.

Sachant que la traversée du Styx dure une heure et que son prix dépend de l'heure de départ, pouvez-vous aidez Joseph Marchand à déterminer l'heure de départ la moins coûteuse ?

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : $N$, nombre de tranches horaires.
  • Sur les lignes suivantes, une liste de $N$ éléments : horaires, liste des tranches horaires avec leur tarifs.
    • Une ligne par élément de la liste : une liste de $3$ entiers séparés par des espaces, respectivement $D$ l'heure de début de l'horaire, $F$ l'heure de fin de l'horaire, $T$ le tarif de l'horaire.

Sortie

Retourne l'heure de départ la moins coûteuse pour Joseph Marchand, la première chronologiquement si plusieurs heures sont optimales.

Contraintes

  • $1 \le N \le 24$
  • $0 \le D \le 23$
  • $1 \le F \le 24$
  • $D \lt F$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
3
0 10 10
10 16 20
16 24 15
Exemple de sortie
17
Commentaire

Ici, Charon propose trois plages horaires.

Si Joseph choisit la première, le mieux est de partir à 9h et d'arriver à 10h, et il devra attendre 18 - 10 = 8h, ce qui nécessite de payer 16 drachmes en hydromel. Le coût total de la traversée et de l'hydromel est donc de 26.

S'il choisit la deuxième plage horaire, il peut partir à 15h et n'attendre que deux heures, pour un coût total de 20 + 4 = 24.

Enfin, s'il choisit la troisième plage horaire il peut partir à 17h et ne payer que le coût de la traversée, c'est-à-dire 15 drachmes.

On voit bien que la meilleure option coûte 15 drachmes, en partant à 17h.

Exemple d'entrée
1
19 23 40
Exemple de sortie
19
Commentaire

Dans ce cas, Joseph arrivera forcément en retard. S'il part le plus tôt possible, soit 19h, il arrivera avec deux heures de retard et devra donc payer deux tournées d'ambroisie pour 8 drachmes. En comptant le prix de la traversée, cela fera 48 drachmes. S'il part plus tard, il devra payer plus de tournées, ainsi la meilleure option est 19h.