Le monde du parfum

Tâche à sortie uniquement

Fichier d'entrée : fragrance.k.in
Fichier de sortie : fragrance.k.out

Cliquez pour télécharger les fichiers d'entrée, pour les systèmes Linux/Unix.

Cliquez pour télécharger les fichiers d'entrée, pour les systèmes windows.

Après quelques expériences professionnelles décevantes dans le monde de la finance, vous avez décidé de faire meilleur usage de vos talents. Vous venez de décrocher un emploi dans l'industrie du parfum et participez à la création des parfums les plus raffinés. La création de nouvelles senteurs est un art qui implique d'essayer de nombreuses combinaisons d'ingrédients, puis de faire appel à un nez entraîné pour évaluer chaque parfum obtenu.

Votre travail consiste à aider ces experts à gagner du temps en générant uniquement les combinaisons d'ingrédients qui sont susceptibles d'être agréables. Pour cela, vous avez collecté des données en demandant aux nez les plus réputés de noter de nombreuses combinaisons de deux ingrédients. Votre théorie est que si toute paire d'ingrédients contenus dans un parfum sent bon, alors ce parfum a de bonne chances de sentir bon également.

On vous fournit un total de N ingrédients (numérotés de 1 à N) et une liste de P paires d'ingrédients distincts et leur note associée. Une note positive signifie que la paire sent bon et une note négative signifie que la paire sent mauvais. Les paires d'ingrédients qui n'ont jamais été évaluées par un expert ne sont pas listées, et doivent être considérées comme étant neutres, avec une note de 0.

Les parfumeurs souhaitent créer une nouvelle senteur composée de K ingrédients exactement. Votre but est de sélectionner un ensemble de K ingrédients différents de telle façon que la somme des notes de toutes les paires d'ingrédients possibles au sein de l'ensemble soit la plus grande possible.

Remarquez que vous ne devez pas nécessairement trouver la solution optimale. Voyez la section Calcul du score pour plus de détails.

Contraintes

  • 2 <= N <= 1000, où N est le nombre d'ingrédients disponibles.
  • 1 <= K <= 20, où K est le nombre d'ingrédients que vous devez inclure dans votre sélection.
  • 1 <= P <= 100 000, où P est le nombre de paires d'ingrédients qui ont été évaluées par des experts.
  • -1000 <= Ri <= 1 000, où Ri est la note d'une paire d'ingrédients.

Entrée

On vous donne 10 fichiers d'entrée, nommés fragrance.M.in (1 <= M <= 10).

La première ligne de chaque fichier d'entrée contiendra les entiers N, K et P, définis plus haut. Chacune des P lignes suivantes contiendra trois entiers: Ai, Bi et Ri, indiquant que la paire d'ingrédients (Ai, Bi) a obtenu la note Ri. On vous garantit que Ai ≠ Bi pour chaque paire, et qu'aucune paire ne sera listée plus d'une fois.

Sortie

Pour chaque fichier d'entrée fragrance.M.in, vous devez produire un fichier de sortie correspondant, fragrance.M.out qui décrit votre ensemble d'ingrédients.

Ce fichier de sortie doit consister en exactement K+1 lignes. La première ligne doit contenir un simple entier, le total des notes de toutes les paires d'ingrédients possibles au sein de votre ensemble. Les K lignes suivantes doivent contenir chacune un entier décrivant l'un des K ingrédients distincts de votre ensemble.

Exemple

entrée : 

5 3 7
1 2 12
1 3 10
1 5 -3
2 4 -2
2 5 -8
3 5 17
4 5 5

sortie : 

24
1
3
5

Commentaires

Dans cet exemple, vous disposez de cinq ingrédients et devez créer un parfum contenant trois d'entre eux. Des experts ont évalué sept paires d'ingrédients et leur ont attribué des notes allant de -8 à 17.

La meilleure sélection possible est constituée des ingrédients 1, 3 et 5. Il se trouve que les trois paires possibles d'ingrédients de cette sélection ont été notées par des experts : la combinaison (1, 3) a reçu une note de 10, la combinaison (1, 5) a reçu une note de -3 et enfin la combinaison (3, 5) a reçu une note de 17, ce qui donne un total pour cette sélection de 10 - 3 + 17 = 24.

Calcul du score

Il n'y a pas de "meilleure solution" particulière que vous devez atteindre. Au lieu de cela, votre score sera déterminé relativement aux soumissions des autres candidats participant à l'épreuve (ainsi qu'aux solutions des juges). On vous garantit qu'il y aura toujours au moins une solution avec une note globale positive, pour chaque scénario d'entrée.

Pour chaque scénario d'entrée, le candidat qui obtient la meilleure note globale sera identifié. Supposez que ce candidat obtienne un parfum ayant une note globale de r. Votre score pour ce scénario d'entrée sera alors :

  • 100% si vous avez fourni une solution ayant également une note globale de r;
  • au moins 10% si vous avez fourni une solution valide;
  • 0% si vous avez fourni une solution incorrecte (par exemple, vous calculez mal la note globale de votre ensemble);
  • sinon, elle sera déterminée par une formule évaluant votre score par rapport à la meilleure note obtenue pour ce scénario d'entrée, comme décrit ci-dessous.

Votre score = 10 + 90 * ( votre résultat / meilleur résultat)5

Par exemple, considérez un scénario d'entrée pour lequel la meilleure solution trouvée est un ensemble ayant une note globale de 40. Votre score pour une solution correcte serait comme suit :

Note globale 0 5 10 15 20 25 30 35 40
Score 10% 10% 10% 10% 12% 18% 31% 56% 100%

Soumettre pour un problème à sortie uniquement

Le site ne gère pas encore la soumission pour ce type de problèmes. Faites un zip contenant vos fichiers, et envoyez le par mail à entraineur@france-ioi.org. Un entraîneur vous indiquera votre score.

Source : https://www.france-ioi.org/ Traduit par : Amaury Pouly.