A Winners’ Staircase
National Olympiad — National round (2009 season)
Submission name: win.cpp
Problem summary
Choose a rectangular sheet from which a symmetric winners’ staircase can be cut with minimum waste. Its base lies along the longer side, and its total height equals the shorter side. It has n equal height levels; each outward step on either side is m cm wide. Report all optimal sheet indices and the waste area.
Input
k; then n and m; then k pairs a, b describing the sheets.
Output
Optimal 1-based indices in ascending order on one line; minimum waste in square centimeters on the next.
Constraints
1 ≤ k, n ≤ 20; 1 < m ≤ a, b ≤ 1,000,000. The shorter side is divisible by n; every sheet can contain the staircase.
Worked example
An independently prepared example for this explanation.
Input
3 3 2 70 60 24 59 16 9
Output
3 72
Solution analysis
- Let H be the shorter side and L the longer side. Each of the n horizontal bands has height H/n. By symmetry, their widths from top to bottom are 2m, 4m, …, 2nm.
- The staircase area is (H/n) × 2m × (1 + 2 + … + n) = mH(n + 1). Subtract this from the full sheet area LH to obtain the waste, then keep every index attaining the minimum.
- For the 16 by 9 sheet with n = 3 and m = 2, the band widths are 4, 8, and 12, each with height 3. Their areas total 72. The full sheet area is 144, so the waste is 72.
Why it works
The diagram consists of n equal-height horizontal bands. Their widths are twice the successive step widths, so summing their areas gives mH(n + 1). Subtracting from the sheet area gives exactly the discarded area. Comparing this value for every sheet and retaining all equal minima yields precisely all optimal indices.
Watch out. The staircase has two mirrored halves: its top is 2m wide and its bottom is 2nm wide. Subtract its area from the entire sheet, including side margins. Use 64-bit arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
int main() {
int k;
long long steps, width;
cin >> k >> steps >> width;
long long best = numeric_limits<long long>::max();
vector<int> indices;
for (int index = 1; index <= k; index++) {
long long a, b;
cin >> a >> b;
long long height = min(a, b);
// Both mirrored halves have total area width * height * (steps + 1).
long long waste = a * b - width * height * (steps + 1);
if (waste < best) {
best = waste;
indices.clear();
}
if (waste == best) {
indices.push_back(index);
}
}
for (size_t i = 0; i < indices.size(); i++) {
if (i > 0) {
cout << ' ';
}
cout << indices[i];
}
cout << '\n' << best << '\n';
}