Course d'éléphants – Épreuve régionale 2015

Niveau 1

Énoncé

Aujourd'hui, Joseph Marchand assiste à une bien étrange course. Les participants ne sont rien d'autre que des éléphants ! Chaque éléphant part d'un endroit donné de la piste, et avance à une vitesse donnée. Aidez Joseph Marchand à gagner ses paris en lui indiquant l'éléphant qui arrivera le premier.

Il n'y a pas d'ex-æquo, l'éléphant gagnant de chaque course arrive à chaque fois avec une marge d'avance d'au moins une unité de temps sur le second.

Entrée

L'entrée contient 4 lignes :

  • Sur la première ligne, le nombre N d'éléphants au départ de la course.
  • Sur la seconde ligne, la longueur L de la piste.
  • Sur la troisième ligne, les vitesses initiales V0, V1, ... des éléphants.
  • Sur la dernière ligne, les positions de départ P0, P1, ... des éléphants.

Sortie

Le numéro de l'éléphant qui atteint le plus vite la ligne d'arrivée. Attention, on numérote les éléphants de 0 à N-1.

Contraintes

  • 0 < N ≤ 20 000
  • 0 < L ≤ 1 000 000
  • 0 < Vi ≤ 2000
  • 0 ≤ Pi < L

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
3
32303
1287 151 1468
30812 4280 4704
Exemple de sortie
0
Commentaire

Ici, trois éléphants prennent le départ sur une piste de 32303 mètres. Le premier démarre à une vitesse de 1287 m/s, le second à 151 m/s, et le troisième à 1468 m/s. Ils partent respectivement du 30812e, du 4280e, et du 4704e mètre, c'est donc l'éléphant numéro 0 sur lequel Joseph Marchand devra parier.