Water in Compartments
National Olympiad — Regional round
Submission name: m3.cpp
Problem summary
A tank of width 1 and length 4S consists of S sectors, separated by walls of height d. Each sector has four unit-width compartments separated by three walls. From left to right the sector wall orders repeat (a,c,b), (b,a,c), (b,c,a), (c,a,b). Water enters the leftmost compartment; K cubic metres have been poured. Report the four water levels in the last sector containing any water. Internal walls have negligible thickness and 0<a<b<c<d; the outer tank is higher than d.
Input
S K, followed by a b c d.
Output
Four levels rounded to three digits after the decimal point.
Constraints
1 ≤ S ≤ 1,000,000; 1 ≤ K ≤ 10¹⁰; 1 ≤ a<b<c<d ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
2 8 1 2 3 5
Output
3.000 3.000 2.000 0.000
Solution analysis
- Every fully passed sector holds 4d water. If all sectors have filled to d, all compartments communicate and have common level K/(4S). Otherwise skip floor((K−1)/(4d)) completely filled sectors; using K−1 ensures an exactly full sector is still the last nonempty one.
- There are only four compartments left to simulate. In any interval of compartments, choose its tallest internal wall h. Until the left portion holds h times its width, recursively pour only into that portion. Next hold the left part at h and pour the remainder into the right portion. Once the whole interval has h times its width, all levels are equal.
Why it works
A wall cannot pass water until the water on its entering side reaches its height. The tallest wall therefore separates two sequential filling phases, followed by a connected equal-level phase. Applying this rule recursively accounts for every unit of water and every barrier. Sector walls are taller than every internal wall, so the skipped-sector reduction is exact.
Watch out. When K is a multiple of 4d, the following empty sector is not the answer. After filling all sectors, water levels may exceed d.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A wall cannot pass water until the water on its entering side reaches its height. The
// tallest wall therefore separates two sequential filling phases, followed by a connected equal-level
// phase.
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
vector<double>wall,level(4);
void pour(int l,int r,double volume){
if(l==r){
level[l]=volume;
return;
}
int m=l;
for(int z=l+1;z<r;z++){
if(wall[z]>wall[m]){
m=z;
}
}
double h=wall[m],left=(m-l+1)*h,total=(r-l+1)*h;
if(volume>=total){
for(int z=l;z<=r;z++){
level[z]=volume/(r-l+1);
}
}
else if(volume<=left){
pour(l,m,volume);
}
else{
for(int z=l;z<=m;z++){
level[z]=h;
}
pour(m+1,r,volume-left);
}
}
int main(){
long long S,K,a,b,c,d;
cin>>S>>K>>a>>b>>c>>d;
if(K>=4*S*d){
fill(level.begin(),level.end(),double(K)/(4*S));
}
else{
long long sector=(K-1)/(4*d),v=K-sector*4*d;
vector<vector<double>>orders={{double(a),double(c),double(b)},{double(b),double(a),double(c)},
{double(b),double(c),double(a)},{double(c),double(a),double(b)}};
wall=orders[sector%4];
pour(0,3,v);
}
cout<<fixed<<setprecision(3);
for(double h:level){
cout<<h<<' ';
}
cout<<'\n';
}