Compatibilité héroique – Épreuve régionale 2021

Niveau 5

Énoncé

Hermès vient d'annoncer une grande quête ! Elle apportera gloire et richesse à ceux qui y participeront. À travers le pays, des centaines de groupes de héros se mobilisent pour remporter le droit de mener la quête.

Seulement voilà, une fois tous les groupes rassemblés, Hermès ne peut pas se permettre d'attribuer la quête à un seul d'entre eux, cela ferait des jaloux.

Il décide donc de créer une nouvelle équipe, composée d'au moins un membre de chacun des groupes présents. Hermès considère que pour que des inconnus s'entendent bien et que leur quête soit un succès, il est nécessaire que leur âge soit le plus proche possible !

Hermès entend donc définir comme critère de sélection le plus petit intervalle d'âge qui permette à au moins un héros de chaque groupe de se présenter.

Les groupes rangent donc leurs membres du plus jeune au plus vieux, et attendent l'intervalle d'Hermès.

Fournis à Hermès un algorithme qui lui permettra de connaître les plus petits intervalles d'âge qui incluent au moins un membre de chaque groupe.

Entrée

L'entrée contiendra :

  • Sur la première ligne, un entier : $n$, le nombre de groupes.
  • Sur la ligne suivante, un entier : $m$, le nombre de membres par groupe.
  • Sur les $n$ lignes suivantes, une liste de $m$ entiers : $groupes$, représentant l'âge de chaque héros du groupe.

Sortie

Afficher les différents couples de valeurs définissant les plus petits intervalles d'âge incluant au moins un membre de chaque groupe. Les couples doivent être affichés du plus jeune au plus vieux.

Contraintes

  • $1 ≤ n ≤ 500$
  • $1 ≤ m ≤ 500$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
3
5
18 31 40 51 60
7 24 32 35 35
9 21 34 42 58
Exemple de sortie
31 34
Commentaire

On a ici 3 groupes de 5 héros. Si l'on observe, par exemple, les plus jeunes héros de chaque groupe, la différence d'âge est de $18-9=9$ ans. Si l'on compare chaque membre de chaque groupe avec ceux des autres groupes, on trouve que le plus petit intervalle d'âge incluant au moins un membre de chaque groupe est $31 34$. En effet, on a pour les groupes, respectivement des héros agés de $31$, $32$ et $34$ ans. La différence d'âge $34-31=3$ est la plus petite trouvable.

Exemple d'entrée
3
6
7 10 24 34 41 47
17 37 52 57 72 81
16 24 30 38 41 51
Exemple de sortie
34 38
37 41
Commentaire

Dans cet exemple, la plus petite différence est $34-38=4$. Il existe en effet des héros âgés par groupe respectif de $34$, $37$ et $38$ ans. De même, l'intervalle $37 41$, de différence $4$ également, fonctionne aussi. Il existe des héros âgés de $41$, $37$ et $38$ ans.