Échange Profitable – Épreuve régionale 2023

Niveau 2

Énoncé

L'architecte ayant terminé ses occupations, il indique aux aventuriers de précieuses informations leur permettant de se repérer dans le temps. Supposant qu'il s'agissait simplement d'un problème de précision lors du placement du dernier point de contrôle, Valérian et Oscar tentent alors d'effectuer un déplacement relatif pour arriver à la bonne année. Oscar consulte de nouveau son manuel, effectue les calculs d'encodage, et indique à Valérian la combinaison à effectuer pour arriver à l'année désirée. L'indicateur temporel s'agite, puis s'arrête à nouveau, mais l'année indiquée n'est toujours pas compréhensible. Seraient-ils alors toujours en Antiquité ? Pendant que Valérian et Oscar continuent leurs investigations sur la cause de ces erreurs, les autres jeunes ressortent de la machine pour évaluer leur avancée temporelle.

Les cinq jeunes amis, partis récolter plus d'informations, se retrouvent dans un marché animé à Delphes. Ils se rendent compte qu'ils se situent dans un commerce où les marchands proposent des objets rares et précieux. Les amis décident de négocier avec l'un des marchands pour obtenir des informations sur leur position dans le temps. Le marchand, surpris de voir des étrangers dans sa boutique, compte profiter de leur situation pour étendre sa collection d'objets précieux.

Afin de briser la glace avec le marchand, l'objectif de nos aventuriers va être d'échanger le plus d'objets possible avec le marchand. Ils commencent par mettre en commun toutes leurs possessions, et réalisent que leur collection comporte précisément autant d'objet que celle du marchand.

On comptabilise la valeur d'une collection comme étant le nombre d'objets distincts présents dans celle-ci. Un échange est une transaction où nos amis et le marchand décident de troquer un de leurs objets. Un échange n'est possible que si la valeur des collections du marchand et de nos amis augmente après celle-ci.

Aidez nos amis à effectuer un nombre maximal d'échanges avec le marchand !

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre d'objets dont vous disposez.
  • Sur les lignes suivantes, une liste de N éléments : vos objets, la liste de vos possessions.
    • Une ligne par élément de la liste : une chaine de 31 caractères ou moins.
  • Sur les lignes suivantes, une liste de N éléments : objets marchand, la liste des possessions du marchand.
    • Une ligne par élément de la liste : une chaine de 31 caractères ou moins.

Sortie

Afficher, sur une ligne, le nombre maximal d'échanges qu'il est possible d'effectuer.

Contraintes

  • $1 \le N \le 100$

Contraintes de performance

  • $1 \le N \le 100\,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
5
montre
casquette
montre
carte
casquette
poterie
bijou
bijou
poterie
bijou
Exemple de sortie
2
Commentaire

Après avoir mis en commun leurs possessions, les jeunes réalisent qu'ils possèdent deux montres, deux casquettes et une carte. La valeur de leur collection est donc de 3. Le marchand, quant à lui, possède deux poteries et trois bijoux. La valeur de sa collection est donc de 2.

Le premier échange peut être d'échanger une montre contre un bijou. Après cet échange, la collection des jeunes est composée d'une montre, de deux casquettes, d'une carte et d'un bijou, et possède donc une valeur de 4. Après cet échange, la collection du marchand est de deux poteries, deux bijoux et une montre, et possède donc une valeur de 3. Les deux collections ont bien augmenté en valeur.

Ensuite, le second échange peut être d'échanger une casquette contre une poterie. Après cet échange, la collection des jeunes est composée d'une montre, d'une casquette, d'une carte, d'un bijou et d'une poterie. La valeur de leur collection atteint ainsi 5. Le marchand, quant à lui, possède alors dans sa collection deux bijoux, une poterie, une montre et une casquette. La valeur de sa collection atteind ainsi 4. Les deux collections ont bien augmenté en valeur.

Il n'est après cela plus possible de réaliser d'échange qui augmenterait la valeur des deux collections. Il n'est pas possible de réaliser plus de deux échanges. La réponse est donc 2.

Exemple d'entrée
4
manuscrit
manuscrit
telephone
ordinateur
manuscrit
tapisserie
manuscrit
statue
Exemple de sortie
0
Commentaire

La collection des jeunes est composée d'un téléphone, d'un ordinateur et de deux manuscrits. La valeur de leur collection est donc de 3. La collection du marchand est composée d'une statue, d'une tapisserie et de deux manuscrits. La valeur de sa collection est donc également de 3.

Malheureusement, aucun échange ne peut augmenter la valeur des deux collections. Puisque aucun échange ne peut être réalisé, la réponse est 0.