Course dans la savane – Épreuve régionale 2019

Niveau 2

Enoncé

Le Lion organise une course de relais sur la plus grande piste de sa savane. $n$ équipes de 3 animaux participent, le but de la course étant de finir les premiers sans que la somme des vitesses des 3 animaux n'excède strictement $v$ km/h. $v$ km/h étant la somme maximale des vitesses pour que guépards comme éléphants puissent participer sans trop d'injustice. Aidez le Lion à déterminer quelle équipe remporte la course sans tricher !

On numérote les équipes de 0 (inclus) à n (exclus).

Si aucune équipe ne remporte la course sans tricher, retourner -1.

On suppose que deux équipes ne peuvent pas finir la course ex aequo.

Entrée

  • Sur la première ligne, un entier : n, le nombre d'équipes participantes.
  • Sur la ligne suivante, un entier : v, le vitesse moyenne à ne pas dépasser.
  • $n$ lignes de 3 entiers, chaque ligne représentant une équipe d'animaux et les entiers leur vitesse respective.

Sortie

  • Le numéro de l'équipe, victorieuse de la course sans avoir triché ($n^\text{ième}$ ligne, où la première ligne est la ligne 0).

Contraintes

  • 0 < $n$ < 100
  • 0 < $v$ < 300
  • 0 < $v_{anim}$ < 101

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
42
1 2 3
20 21 1
2 19 98
Exemple de sortie
1
Commentaire

Ici, trois équipes participent à la course. La vitesse à ne pas dépasser est de 42 km/h. L'équipe n°0 : trois animaux dont la somme des vitesses est 1 + 2 + 3 = 6 km/h. 6 <= 42 donc la première équipe n'est pas disqualifiée pour triche. L'équipe n°1 : trois animaux dont la somme des vitesses est 20 + 21 + 1 = 42 km/h pile. 42 <= 42 donc la seconde équipe n'est pas disqualifiée pour triche. L'équipe n°2 : trois animaux dont la somme des vitesses est 2 + 19 + 98 = 119 km/h. Ici, 119 > 42 donc la troisième équipe est disqualifiée.

Enfin, parmi les deux équipes qui n'ont pas trichées, c'est l'équipe n°1 qui est la plus rapide. On renvoie donc 1.