Exactly Enough Eggs
National Olympiad — Regional round (2010 season)
Submission name: provident.cpp
Problem summary
Eggs are sold in boxes of 6 and 8. Buy exactly n eggs with the fewest boxes, or report that this is impossible.
Input
One integer n.
Output
The minimum box count, or No solution.
Constraints
6 ≤ n ≤ 100.
Worked example
An independently prepared example for this explanation.
Input
20
Output
3
Solution analysis
- Try every possible number x of eight-egg boxes from 0 through floor(n/8). The remaining eggs are n − 8x.
- A candidate is feasible exactly when the remainder is divisible by 6. It then uses x + (n − 8x)/6 boxes. Keep the smallest feasible count.
- For 20 eggs, one eight-egg box leaves 12 eggs, supplied by two six-egg boxes. The total is three boxes. An odd demand such as 15 is impossible.
Why it works
Any valid purchase has some number x of eight-egg boxes within the enumerated range. The divisibility test finds exactly the corresponding purchases of six-egg boxes. Thus every feasible purchase is considered and the smallest box count is optimal; absence of a candidate proves impossibility.
Watch out. Minimize boxes rather than eggs. Print the exact two-word message when no combination exists.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int eggs;
cin >> eggs;
int best = eggs + 1;
for (int eights = 0; 8 * eights <= eggs; eights++) {
// Once the eight-egg boxes are fixed, the six-egg count is forced.
int remaining = eggs - 8 * eights;
if (remaining % 6 == 0) {
best = min(best, eights + remaining / 6);
}
}
if (best == eggs + 1) {
cout << "No solution\n";
} else {
cout << best << '\n';
}
}