Order Excavations by First-Trip Soil Volume
National Olympiad — National round (2009 season)
Submission name: soil.cpp
Problem summary
Sort excavations by whole cubic metres removed before their retained staircase is excavated, breaking ties by site index.
Input
n; each site gives h a b in metres, l m in centimetres, then k steps. Real values have at most two decimal places.
Output
The sorted1-based site indices.
Constraints
2 ≤ n ≤20;2 ≤ k ≤50;0 ≤ a,b,h,l ≤1150; the source states0 ≤ m ≤a,b. Inputs describe the stated staircase geometry.
Worked example
Input and output for the worked example discussed below.
Input
2 15.01 23.00 39.50 4 9 10 4.26 18.18 24.50 3 15 5
Output
2 1
Solution analysis
- Full volume is hab. The retained step blocks have common footprint(l/100)(m/100) and heights h/(k+1),2h/(k+1),…,kh/(k+1). Their height sum is hk/2, so retained volume is lmhk/20000.
- Parse decimal values exactly as hundredths. For scaled H,A,B,L,M, removed volume is H×X/D with X=20000AB−LMk and D=2×10^10. Avoid an overflowing H×X by evaluating H×(X/D)+(H×(X%D))/D.
- Sort the resulting integer part and index. Different fractions can have the same whole-cubic-metre priority, so sorting before truncating is wrong. Site2 in the sample has smaller first-removal volume and appears first.
Why it works
The triangular step-height sum proves the retained-volume formula. Exact scaling preserves all given decimal values. X=Dq+r implies the integer part is Hq+trunc(Hr/D), using safe intermediates. Pair ordering then implements both required keys.
Watch out. Convert centimetres to metres, avoid floating-point floor at integer boundaries, divide the scaled numerator safely, and break whole-volume ties by index.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
long long readHundredths(){
string text;
cin>>text;
size_t dot=text.find('.');
if(dot==string::npos){
return stoll(text)*100;
}
string fraction=text.substr(dot+1);
while(fraction.size()<2){
fraction+='0';
}
return stoll(text.substr(0,dot))*100+stoll(fraction);
}
int main(){
int n;
cin>>n;
vector<pair<long long,int>>order;
const long long denominator=20000000000LL;
for(int index=1;index<=n;index++){
long long h=readHundredths();
long long a=readHundredths();
long long b=readHundredths();
long long l=readHundredths();
long long m=readHundredths();
int k;
cin>>k;
long long x=20000*a*b-l*m*k;
// Multiply the bounded remainder separately instead of forming h*x.
long long whole=h*(x/denominator)+h*(x%denominator)/denominator;
order.push_back({whole,index});
}
sort(order.begin(),order.end());
for(int i=0;i<n;i++){
if(i>0){
cout<<' ';
}
cout<<order[i].second;
}
cout<<'\n';
}