ChemicalMixing
Rookie SRM 4 · 2021-04-09 · by t-mac
Problem Statement
Your lab has several containers of a certain type of chemical, each with varying volume, and varying quantity of dissolved solute. The strength of any container can be calculated as solute / volume. volume[i] and solute[i] represent the volume and quantity of solvent in container i.
You now wish to mix a batch of the chemical, and can do so only by using the entirety of some subset of the available containers. That is, you cannot use part of what is left in any container, you must use all or none of each container. You need to produce at least minQuantity volume total after mixing, and you want the end result to have a strength as close as possible to desiredStrength. Compute the absolute difference between the desired strength and the closest strength you can create by mixing checmicals to obtain the minimum required volume.
Notes
- * A return value that is within 1e-9 of the actual result is considered correct.
Constraints
- volume will have between 1 and 50 elements, inclusive.
- Each element of volume will be between 1 and 100, inclusive.
- solute will have the same number of elements as volume.
- Each element of solute will be between 0 and 20, inclusive.
- minVolume will be between 1 and the sum of all elements of volume.
- desiredStrength will be between 0 and 10, inclusive.
{10, 10}
{1, 4}
5
0.20
Returns: 0.04999999999999999
Either container is sufficient volume on it's own, but the strength would be 0.1 or 0.4, a difference from our desired strength by 0.1 or 0.2. However, if we combine the two, the resultant strength of the chemical is 0.25, an error of only 0.05, which is better.
{10, 10, 10, 10}
{ 5, 5, 5, 0}
35
0.5
Returns: 0.125
Although the first three containers are exactly the right strength, we need to mix all four containers to get a sufficient volume. The resulting strength is 0.375, an error of 0.125.
{ 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 35, 27, 98, 15, 48, 72, 23, 88}
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 0, 1, 2, 3, 4, 5, 6, 7, 8}
1
0.1
Returns: 0.0
{20, 20, 20}
{15, 15, 0}
40
0.5
Returns: 0.0
Although any two containers would suffice to meet the required volume, if we use all three, we can precisely hit the desired strength.
{50, 50, 50, 50}
{12, 4, 20, 0}
100
0.5
Returns: 0.18
Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChemicalMixing with a public method double closestBlend(vector<int> volume, vector<int> solute, int minVolume, double desiredStrength) · 46 test cases · 2 s / 256 MB per case