Mushrooms Near One Hundred
National Olympiad — Municipal round (2021 season)
Submission name: supermario.cpp
Problem summary
Mario encounters ten mushrooms in order and may stop after taking a prefix of them. Choose the total price closest to 100. If two totals are equally close, choose the larger total.
Input
Ten positive integer mushroom prices, one per line.
Output
The chosen prefix total.
Constraints
1 ≤ each price ≤ 100. There are exactly ten mushrooms.
Worked example
An independently prepared example for this explanation.
Input
10 20 30 40 50 60 70 80 90 100
Output
100
Solution analysis
- Accumulate the mushroom prices in their given order. Every point where Mario can stop corresponds to one prefix sum; do not reorder mushrooms or skip a prefix.
- Compare abs(sum−100) with the best distance. On an equal distance, prefer the larger sum. Testing every prefix keeps the rule explicit.
- For ten prices of 40, the nearby prefix sums are 80 and 120. Both are 20 away from 100, so choose 120. In the official first sample, the first four mushrooms total exactly 100, which cannot be improved.
Why it works
Every legal stopping point produces exactly one prefix sum examined by the loop. The update rule retains the closest examined total, choosing the larger on ties, so after ten prefixes it is optimal over all legal choices.
Watch out. The mushroom order matters: choose a prefix, not an arbitrary subset or a later-starting interval. Equal distances favor exceeding 100.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
int sum = 0;
int best = 0;
for (int i = 0; i < 10; i++) {
int price;
cin >> price;
sum += price;
// Compare whole prefixes; larger totals win equal distances.
if (abs(sum - 100) < abs(best - 100) ||
(abs(sum - 100) == abs(best - 100) && sum > best)) {
best = sum;
}
}
cout << best << '\n';
}