Best Revenue from Nuts
National Olympiad — Regional round (2026 season)
Submission name: nuts.cpp
Problem summary
For each nut type, ordinary and premium stock can be sold separately at their own prices, or combined and sold at the arithmetic mean of those two prices. Choose independently for every type to maximize total revenue when all stock is sold.
Input
N. Then N lines: kg1 g1 euros1 cents1 kg2 g2 euros2 cents2, describing quantities and prices per 100 grams.
Output
Maximum revenue as two integers: euros and cents.
Constraints
1 ≤ N ≤ 50; 0 ≤ kg1,kg2 ≤ 5; 0 ≤ g1,g2 < 1000, divisible by 100; both quantities positive. Prices are positive, euros ≤ 5 and cents < 100; cents1+cents2 is even.
Worked example
An independently prepared example for this explanation.
Input
1 0 500 1 0 0 100 2 0
Output
9 0
Solution analysis
- Convert every quantity to 100-gram units: 10·kg + g/100. Convert every price to cents: 100·euros + cents. Integer arithmetic then represents all prices exactly.
- Separate revenue is quantity1·price1 + quantity2·price2. Mixed revenue is (quantity1 + quantity2)·(price1 + price2)/2. The input guarantees the mean price is a whole number of cents.
- Add the larger revenue for this type to the answer. No choice affects another type: there are no shared capacity or mixing restrictions.
- In the example, separate sales earn 5·100 + 1·200 = 700 cents. Mixing earns 6·150 = 900 cents, so print 9 0. The mean is of the two prices, not a quantity-weighted mean.
Why it works
Total revenue is the sum of independent per-type revenues. Replacing any type’s choice with its better option cannot harm another type, so choosing the maximum for every type produces a globally maximum sum.
Watch out. Prices apply to 100 grams, not one gram. Use the arithmetic mean of the two listed prices; a weighted mean would erase the opportunity described by the problem. Output cents as an integer, not a decimal fraction.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int typeCount;
cin >> typeCount;
int totalCents = 0;
for (int type = 0; type < typeCount; type++) {
int kg1, grams1, euros1, cents1;
int kg2, grams2, euros2, cents2;
cin >> kg1 >> grams1 >> euros1 >> cents1 >> kg2 >> grams2 >> euros2 >> cents2;
int quantity1 = 10 * kg1 + grams1 / 100;
int quantity2 = 10 * kg2 + grams2 / 100;
int price1 = 100 * euros1 + cents1;
int price2 = 100 * euros2 + cents2;
int separateRevenue = quantity1 * price1 + quantity2 * price2;
int meanPrice = (price1 + price2) / 2;
int mixedRevenue = (quantity1 + quantity2) * meanPrice;
// Each type can be optimized independently of all other types.
totalCents += max(separateRevenue, mixedRevenue);
}
cout << totalCents / 100 << ' ' << totalCents % 100 << '\n';
}