Pancakes
National Olympiad — Regional round (2012 season)
Submission name: pancakes.cpp
Problem summary
There are n independent hotplates. Hotplate i needs ti seconds per pancake, and one pancake must stay on a single hotplate. Find the earliest time when x pancakes can be ready.
Input
x and n, followed by the n cooking times.
Output
The minimum number of seconds.
Constraints
0 < x < 10^15; 0 < n < 20; 1 ≤ ti < 500.
Worked example
Official statement sample.
Input
3 2 50 70
Output
100
Solution analysis
- In T seconds hotplate i finishes floor(T/ti) pancakes. Start every hotplate immediately and keep it busy; their capacities add because they work independently.
- The total capacity never decreases with T. Binary search the first feasible time between 0 and x times the fastest cooking time. This upper bound corresponds to using that hotplate alone.
- For the sample, time 99 gives only one pancake on each hotplate. At time 100 the first finishes its second pancake, making three in total.
Why it works
No schedule can make a hotplate complete more than floor(T/ti) pancakes by T. Continuous operation attains all these bounds simultaneously, so their sum is an exact feasibility criterion. Binary search returns its first true time.
Watch out. Use 64-bit arithmetic for the answer and upper bound. Stop accumulating once capacity reaches x.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
long long x;
int n;
cin>>x>>n;
vector<int>t(n);
for(int&v:t){
cin>>v;
}
long long low=0;
long long high=x**min_element(t.begin(),t.end());
// Capacity is monotone in elapsed time; locate its first feasible value.
while(low<high){
long long mid=low+(high-low)/2;
long long made=0;
for(int v:t){
made+=mid/v;
if(made>=x){
break;
}
}
if(made>=x){
high=mid;
}
else{
low=mid+1;
}
}
cout<<low<<'\n';
}