Compatibilité héroique – Regional event 2021

Level 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$

Runtime constraints

Maximum memory usage
9000 kilobytes
Maximum execution time
6000 milliseconds

Input/output samples

Sample input
3
5
18 31 40 51 60
7 24 32 35 35
9 21 34 42 58
Sample output
31 34
Note

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.

Sample input
3
6
7 10 24 34 41 47
17 37 52 57 72 81
16 24 30 38 41 51
Sample output
34 38
37 41
Note

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.

Submit your solution

You have to register or log in to be able to submit your solution.