Classe d'Âge – Qualification 2026

Niveau 2 ⋅ Validation weight: 40%

Énoncé

Joseph commence à établir sa base de connaissances sur la population robotique. En regardant leurs registres, il remarque que l'historique du groupe de robots de la ville est incohérent.

Heureusement, dans l'historique se trouve la répartition des robots suivant les classes d'âge lors de 2 années différentes séparées par $T$ années. Une classe d'âge est un intervalle défini par une borne inférieure (incluse) et une borne supérieure (exclue). La dernière classe d'âge correspond à tous les robots avec un âge supérieur à la borne la plus élevée.

Joseph veut donc savoir combien de robots ont rejoint le groupe et combien sont partis au cours de ces $T$ années.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de classes d'âge.
  • Sur la ligne suivante, un entier : T, écart de temps entre les deux recensements.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : bornes, la liste des bornes des classes d'âge.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : avant, la liste du nombre de robots par classe d'âge lors du premier recensement.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : apres, la liste du nombre de robots par classe d'âge lors du second recensement.

Sortie

Afficher sur une ligne le nombre minimum de nouveaux robots et sur une seconde ligne le nombre de robots partis

Contraintes

  • $1 \le N \le 10$
  • $1 \le T \le 50$

Contraintes de performance

  • $1 \le N \le 10\,000$
  • $1 \le T \le 10\,000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
2
5
0 10
10 0
5 5
Exemple de sortie
0
0
Commentaire

Ici, 5 robots avaient entre 0 (inclus) et 5 ans (exclus) et 5 entre 5 (inclus) et 10 ans (exclus). 5 ans plus tard, 5 robots ont entre 5 (inclus) et 10 ans (exclus) (1ère classe d'âge) et 5 autres ont 10 ans ou plus (2nde classe d'âge). Schéma

Exemple d'entrée
5
20
0 25 40 50 70
0 3 1 0 0
0 1 1 1 1
Exemple de sortie
2
2
Commentaire

Initialement, il y a 1 robot ayant entre 40 et 50 ans (3e classe d'âge). 20 ans plus tard, il a donc entre 60 et 70 ans, il est donc dans la 4e classe d'âge. De même, les robots de la 2e classe d'âge (25 à 40 ans) devraient tous se trouver dans la 3e ou 4e classe d'âge (40 à 50 ans ou 50 à 70 ans). Il n'y a pourtant qu'un robot dans celles-ci. Par conséquent, 2 robots sont partis. On trouve en plus un robot dans la 2e classe d'âge et un autre dans la 5e classe d'âge ; ces 2 robots sont par conséquents arrivés.