Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]
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 AiBi 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.

Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.

Correction en cours de chargement…