Raise the Poorest Piles
Autumn Tournament (2009)
Submission name: rich.cpp
Problem summary
Repeatedly add one coin to a currently smallest pile until N bank coins have been spent. Determine the final minimum pile size. The last integer in the input is N; all preceding integers are the initial pile sizes.
Input
A whitespace-separated sequence of positive integers ending at EOF: pile sizes followed by N. There is no pile-count field.
Output
The minimum pile size after all N additions.
Constraints
At most 10^7 piles; initial pile sizes≤1000; 0<N≤2^31; source memory limit 10 MB.
Worked example
Original statement sample.
Input
3 10 7 7 12 20
Output
11
Solution analysis
- The last token is special, so keep one pending token while reading. Whenever a new integer arrives, the previous pending value is known to be a pile size; increment its frequency. At EOF the pending value is the bank balance N. Only 1001 counters are needed.
- For a proposed minimum h, the number of coins required is cost(h)=Σ count[v]·max(0,h−v). This cost increases with h, so binary-search the largest h with cost(h)≤N. Any leftover coins are insufficient to raise every currently smallest pile once more, so the final minimum remains h.
- The sample piles are 3,10,7,7,12 and the bank has 20 coins. Raising all piles below 11 costs 8+1+4+4=17. Raising the minimum to 12 would cost 9+2+5+5=21, which is too expensive. The answer is therefore 11.
Why it works
To reach minimum h every deficient pile needs at least h−v additions; these additions are also sufficient. The repeated-smallest process completes exactly such levels before starting the next one. Thus the final minimum is precisely the greatest feasible h, found by monotone binary search.
Watch out. Do not interpret the first token as the number of piles. The input is delimited by EOF and its last token is the bank balance. Remaining coins may be distributed unevenly without increasing the minimum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
array<long long,1001>count{};
long long pending;
cin>>pending;
long long next;
while(cin>>next){
// Only the last input value is not a pile size.
count[static_cast<int>(pending)]++;
pending=next;
}
long long coins=pending;
long long low=0;
long long high=1000+coins;
while(low<high){
long long middle=low+(high-low+1)/2;
long long cost=0;
for(int value=1;value<=1000;value++){
cost+=count[value]*max(0LL,middle-value);
}
if(cost<=coins){
low=middle;
}
else{
high=middle-1;
}
}
cout<<low<<'\n';
}