P9274 [AGM 2023 Qualifier] Construction Plan

A group of engineers is planning to build a new factory. To make their factory reliable, they want to produce various items at a constant and steady rate in units per second. They can use different machines to craft these materials. Each machine has its own speed, which affects the crafting process. Each material has its own crafting recipe, and it must be executed on a specific machine. You are given the description of each machine and the recipes for every required material and intermediate material. You are also given a list of materials that must be produced at a specified rate so that the factory is reliable. We say a machine configuration is optimal if and only if, after removing any single machine from the configuration, the production rate of at least one material becomes lower than the required rate. You need to find an optimal configuration.

The first line contains an integer $M(1≤M≤100)$, the number of machine types we have. In the next $M$ lines, each line contains a string $n(1≤|n|≤30)$ and a number $s(0.01≤s≤100)$, representing the machine name and its speed. The next line contains an integer $N(1≤N≤100)$, the number of recipes. Then follow $N$ groups of recipes. For each recipe group: in the first line of the recipe, a string $p(1≤|p|≤30)$ is the name of the material to be crafted, a string $l(1≤|l|≤30)$ is the name of the machine used in the crafting process, and a number $t(0.01≤t≤100)$ is the time (in seconds) required to craft the material at normal speed. On the next line, there is a number $k(0≤k≤15)$, the number of types of additional materials required to produce this material. In the following $k$ lines, each line contains a string $n(1≤|n|≤30)$, the name of a required material, and an integer $c(1≤c≤10)$, the number of units of that material required. The next line contains an integer $Q(1≤Q≤100)$, the number of demands. Each of the next $Q$ lines contains a string $m(1≤|m|≤30)$, the name of the material that must be produced for this demand, and an integer $c(1≤c≤10)$, the number of units of that material that must be produced per second. Both $s$ and $t$ are floating-point numbers with two decimal places. It is guaranteed that an optimal configuration exists. It is guaranteed that in an optimal solution, the production rate of each material does not exceed $10^9$ units per second, and each material can be crafted using a unique recipe. It is also guaranteed that the dependency graph of recipe requirements has no cycles.

Output a total of $N$ lines. On the $i$-th line, output $p_i,l_i,r_i$, where $r_i$ is the number of machines used to execute the $i$-th recipe.

Translated by ChatGPT 5