Porte crochetée – Épreuve régionale 2022

Niveau 1

Énoncé

La première porte que vous rencontrez est vérouillée par un grand nombre de serrures. Chaque serrure possède un type allant de $1$ à $N$, et il est nécessaire d'avoir autant de clés que de serrures de chaque type pour pouvoir ouvrir la porte.

Par exemple, si la porte possède trois serrures de type 1 et deux serrures de type 2, alors il vous faudra trois clés de type 1 et deux clés de type 2 pour ouvrir la porte.

Heureusement, un serrurier qui se trouvait dans les alentours vous propose d'échanger deux clés d'un même type contre une clé d'un type différent, et à souhait.

Pour toutes les serrures que vous ne pouvez toujours pas ouvrir, il ne vous reste qu'une seule solution : les crocheter.

Vu que crocheter une serrure prend un temps considérable, votre objectif est de déterminer le nombre minimal de serrures que vous devrez crocheter.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de serrures différentes qui existent.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : serrures, le nombre de serrures de chaque type présentes sur la porte.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : cles, le nombre de clés de chaque type que vous possédez.

Sortie

Afficher le nombre de serrures que vous devrez crocheter au minimum.

Contraintes

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

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
2 3 1
4 2 1
Exemple de sortie
0
Commentaire

Vous pouvez échanger au serrurier vos deux clés de type 1 en trop pour une clé de type 2. Vous aurez alors suffisamment de clés pour ouvrir la porte sans crocheter une seule serrure.

Exemple d'entrée
3
1 2 3
4 3 1
Exemple de sortie
1
Commentaire

Vous pouvez ici échanger deux de vos quatre clés de type 1 en une clé de type 3. Il ne vous manquera plus qu'une serrure de type 3 que vous devrez crocheter pour ouvrir la porte.