L'Hydromel – Épreuve régionale 2024

Niveau 3 ⋅ Validation weight: 25%

Énoncé

Les Vikings décident de partir piller le Royaume d'Angleterre. Avant de prendre les mers, le chef de guerre vous charge de préparer le plus d'hydromel possible. Ayant une quantité de miel limitée, vous allez devoir trouver une solution optimale pour produire le plus d'alcool possible.

Vous disposez de plusieurs recettes. Chaque recette indique :

  • Un coût en quantité de miel par litre d'hydromel : cout miel,
  • Une quantité d'alcool produite par litre d'hydromel : ethanol,
  • Une limite de production de la recette : limite.

Pour chaque recette, vous pouvez en produire un certain nombre de litres $l$ (pas forcément entier) inférieur ou égal à sa limite. Cela vous coûte une quantité $l \times \text{cout miel}$ de miel, mais vous procure une quantité $l \times \text{ethanol}$ d'alcool.

Indiquez la quantité maximale d'alcool que vous pouvez produire, sachant que vous disposez d'un maximum de quantite miel quantités de miel.

La réponse n'est pas nécessairement un nombre entier.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : nombre recettes, le nombre de recettes.
  • Sur les lignes suivantes, une liste de nombre recettes éléments : recettes, la liste des recettes.
    • Une ligne par élément de la liste : séparés par des espaces, un entier ethanol la quantité d'ethanol pour un litre de boisson, un entier cout miel, la quantité de miel pour produire un litre de boisson, et un entier limite le nombre de litres maximal de boisson pouvant être produits depuis cette recette.
  • Sur la ligne suivante, un entier : quantite miel, la quantité de miel dont vous disposez

Sortie

Affichez, sur une ligne, la quantité maximale d'alcool que vous pouvez concocter pour les vikings à l'aide des ingrédients dont vous disposez.

Vous devez afficher la quantité sous format décimal, avec une précision d'au moins 0.001.

Attention au formatage et à la taille des nombres ! Il faut bien afficher au format décimal. Une sortie comme 1e+09 peut ne pas être acceptée.

Contraintes

  • $1 \le \text{nombre recettes} \le 10$
  • $0 \le \text{quantite miel} \le 100$
  • $1 \le \text{ethanol} \le 20$
  • $1 \le \text{cout miel} \le 100$
  • $1 \le \text{limite} \le 10$

Contraintes de performance

  • $1 \le \text{nombre recettes} \le 200\,000$
  • $0 \le \text{quantite miel} \le 1\,000\,000\,000$
  • $1 \le \text{ethanol} \le 1\,000$
  • $1 \le \text{cout miel} \le 1\,000\,000\,000$
  • $1 \le \text{limite} \le 1\,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
3
4 4 2
3 3 1
1 2 4
14
Exemple de sortie
12.5
Commentaire

Dans cet exemple, il existe trois recettes :

  • La première recette nous octroie 4 unités d'éthanol par litre d'hydromel, et coûte 4 unités de miel par litre d'hydromel. Nous pouvons produire au maximum deux litres d'hydromel par cette recette.
  • La seconde recette nous octroie 3 unités d'éthanol par litre d'hydromel, et coûte 3 unités de miel par litre d'hydromel. Nous ne pouvons produire qu'un litre d'hydromel par cette recette.
  • La dernière recette nous octroie 1 unité d'éthanol par litre d'hydromel, et coûte 2 unités de miel par litre d'hydromel. Nous pouvons produire jusqu'à quatre litres d'hydromel par cette recette.

Nous disposons de 14 unités de miel. Il est possible d'obtenir 12.5 quantités d'éthanol de la manière suivante :

  • Concocter deux litres d'hydromel depuis la première recette, pour 8 unités de miel. Cela nous procure 8 unités d'éthanol ;
  • Concocter un litre d'hydromel depuis la seconde recette, pour 3 unités de miel. Cela nous procure 3 unités d'éthanol supplémentaires ;
  • Enfin, concocter 1.5 litres depuis la dernière recette, pour 3 unités de miel. Cela nous procure 1.5 unités d'éthanol supplémentaires.

Cette solution apporte 12.5 unités d'éthanol au total. Il n'est pas possible d'obtenir plus d'éthanol avec les ingrédients et limites données.

Exemple d'entrée
3
5 2 3
8 4 2
3 1 5
20
Exemple de sortie
46.0
Commentaire

Dans cet exemple, il existe trois recettes :

  • La première recette nous octroie 5 unités d'éthanol par litre d'hydromel, mais coûte 2 unités de miel par litre d'hydromel. Nous pouvons produire au maximum 3 litres d'hydromel par cette recette ;
  • La deuxième recette nous octroie 8 unités d'éthanol par litre d'hydromel, mais coûte 4 unités de miel par litre d'hydromel. Nous pouvons produire au maximum 2 litres d'hydromel par cette recette ;
  • La dernière recette nous octroie 3 unités d'éthanol par litre d'hydromel, et coûte 1 unité de miel par litre. Nous pouvons produire au maximum 5 litres d'hydromel par cette recette.

Nous disposons de 20 unités de miel, ce qui est suffisant pour concocter toutes les recettes à leur quantité maximale.

Au total, on produit alors :

  • 3 litres d'hydromel à 5 unités d'éthanol par litre, soit 15 unités d'éthanol ;
  • 2 litres d'hydromel à 8 unités d'éthanol par litre, soit 16 unités d'éthanol ;
  • 5 litres d'hydromel à 3 unités d'éthanol par litre, soit 15 unités d'éthanol .

Au total, nous pouvons donc produire 46 unités d'éthanol.

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

Dans cette situation, une seule recette est disponible. La recette propose de concocter au maximum un litre d'hydromel, à un litre d'éthanol par litre d'hydromel. Cette recette coûte trois unités de miel pour fabriquer un litre d'hydromel.

Cependant, nous ne disposons que de deux unités de miel. Nous pouvons donc fabriquer $\frac23$ litres d'hydromel, ce qui nous procure au maximum $\frac23$ unités d'éthanol.

Notez que, parmi d'autres, des sorties acceptées seraient :

  • 0.666
  • 0.667
  • 0.66666666
  • 0.665903

Toute sortie décrivant un nombre décimal entre $\frac23 - 0.001$ et $\frac23 + 0.001$ est acceptée.