Stack Three Cakes
National Olympiad — Municipal round (2014 season)
Submission name: cakes.cpp
Problem summary
Stack three cakes so no wider cake sits on a narrower one and no heavier cake sits on a lighter one. A valid stack is guaranteed. Print cake indices from bottom to top.
Input
Three lines, each containing weight in grams and diameter in centimetres. Cake indices are 1,2,3 in input order.
Output
The three cake indices, bottom first, separated by spaces.
Constraints
Weights 500…10000; diameters 10…100. The cakes have different weights and diameters, and can be stacked validly.
Worked example
An independently prepared example for this explanation.
Input
1000 25 800 15 2500 45
Output
3 1 2
Solution analysis
- A valid bottom-to-top order has decreasing diameter. Since all diameters differ, sorting by diameter uniquely determines that order.
- The existence guarantee means this same order also has decreasing weight. Keep each cake’s original index while sorting.
- The diameters 45,25,15 belong to cakes 3,1,2. Their weights also decrease, so print 3 1 2.
Why it works
Any valid stack must arrange the distinct diameters in descending order. The guaranteed valid arrangement therefore has exactly the sorted order, so it also satisfies the weight condition.
Watch out. Input gives weight first and diameter second. Output original indices, not dimensions or weights.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Cake {
int weight;
int diameter;
int index;
};
int main() {
vector<Cake> cakes(3);
for (int i = 0; i < 3; i++) {
cin >> cakes[i].weight >> cakes[i].diameter;
cakes[i].index = i + 1;
}
// The existence guarantee makes descending diameter also weight-safe.
sort(cakes.begin(), cakes.end(), [](const Cake &a, const Cake &b) {
return a.diameter > b.diameter;
});
cout << cakes[0].index << ' ' << cakes[1].index << ' ' << cakes[2].index << '\n';
}