Mixing the Party Drinks
National Olympiad — National round (2022 season)
Submission name: party.cpp
Problem summary
There are N juice types, with A[i] litres available. A cocktail uses the types in the ratio B[1]:…:B[N]. Mix the largest possible amount, allowing fractional litres, and report how much of each juice remains.
Input
N; N available amounts A[i]; then N recipe ratios B[i].
Output
N leftover quantities in litres, each to two digits after the decimal point.
Constraints
3 ≤ N ≤ 100; 1 ≤ A[i] ≤ 500; 1 ≤ B[i] ≤ 50.
Worked example
An independently prepared example for this explanation.
Input
5 10 15 18 11 4 3 4 1 2 1
Output
0.00 1.67 14.67 4.33 0.67
Solution analysis
- Let k be the common recipe scale. Using k·B[i] litres of type i requires k ≤ A[i]/B[i] for every juice. The maximum scale is the smallest of these ratios.
- Find the limiting juice using exact cross multiplication of the small integer inputs, then calculate each leftover as A[i]−k·B[i]. Fractional scales are allowed; do not round the scale down to an integer.
- In the sample, type 1 limits k to 10/3. It is used completely. Type 2 leaves 15−4·10/3 = 5/3 litres, displayed as 1.67. The same calculation gives the other leftovers.
Why it works
Every legal mixture scale satisfies all resource bounds and therefore cannot exceed their minimum. At that minimum no type is overused and at least one is exhausted, so it is feasible and maximum. Subtracting its consumption gives exactly the leftovers.
Watch out. Use fixed two-decimal formatting. Fractional batches are allowed. Compute leftovers using a nonnegative integer numerator to avoid printing negative zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> available(n);
vector<int> ratio(n);
for (int& value : available) {
cin >> value;
}
for (int& value : ratio) {
cin >> value;
}
int limiting = 0;
for (int i = 1; i < n; i++) {
if (available[i] * ratio[limiting] < available[limiting] * ratio[i]) {
limiting = i;
}
}
cout << fixed << setprecision(2);
for (int i = 0; i < n; i++) {
// Exact subtraction keeps an exhausted juice at positive zero.
int numerator = available[i] * ratio[limiting] - available[limiting] * ratio[i];
double leftover = static_cast<double>(numerator) / ratio[limiting];
if (i > 0) {
cout << ' ';
}
cout << leftover;
}
cout << '\n';
}