Cheapest Combination of Two Vehicle Types
National Olympiad — National round (2012 season)
Submission name: decision.cpp
Problem summary
Transport at least K students simultaneously using buses of capacity N costing X and minibuses of capacity M costing Y. Find the uniquely cheapest nonnegative vehicle counts.
Input
X Y N M K.
Output
The number of buses and minibuses.
Constraints
1 < X,Y,N,M,K < 5000; the cheapest solution is unique.
Worked example
Input and output for the worked example discussed below.
Input
700 200 30 8 41
Output
1 2
Solution analysis
- Enumerate the number of buses from zero through ceil(K/N). No larger count is useful because buses alone already carry everyone and all costs are positive.
- For each fixed bus count, the uncovered demand is max(0,K−buses×N). Its cheapest completion uses exactly ceil(uncovered/M) minibuses; extra minibuses only increase cost.
- For 41 students, one 30-seat bus leaves 11 seats of demand, requiring two 8-seat minibuses and costing 1100. Two buses cost 1400 and six minibuses cost 1200, so output 1 2.
Why it works
Every potentially optimal bus count appears in the enumeration. For each count the minimum feasible minibus count is uniquely determined by remaining demand and positive costs. The smallest candidate cost is therefore the global minimum.
Watch out. Capacity may exceed demand. Use ceiling division, and permit zero vehicles of either type. The five input numbers are costs first, capacities second.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
using namespace std;
int main(){
int busCost;
int taxiCost;
int busCapacity;
int taxiCapacity;
int students;
cin>>busCost>>taxiCost>>busCapacity>>taxiCapacity>>students;
int bestCost=numeric_limits<int>::max();
int bestBuses=0;
int bestTaxis=0;
for(int buses=0;buses<=(students+busCapacity-1)/busCapacity;buses++){
int remaining=max(0,students-buses*busCapacity);
// Positive costs make the smallest feasible completion optimal.
int taxis=(remaining+taxiCapacity-1)/taxiCapacity;
int cost=buses*busCost+taxis*taxiCost;
if(cost<bestCost){
bestCost=cost;
bestBuses=buses;
bestTaxis=taxis;
}
}
cout<<bestBuses<<' '<<bestTaxis<<'\n';
}