Courier Prices
Autumn Tournament (2019)
Submission name: trans.cpp
Problem summary
Choose either of two couriers separately for each of two deliveries, minimizing their total cost. For distance x km, courier 1 charges 4 lev up to 5 km, 7 up to 10, 12 up to 20, 17 up to 30, otherwise 57 stotinki per whole kilometre. Courier 2 charges a fixed fee plus a rate per whole kilometre: up to 2 km (90, 90), up to 5 (100, 85), up to 20 (125, 80), up to 40 (325, 70), otherwise (925, 55), with both numbers in stotinki.
Input
Two integer delivery distances in metres.
Output
The minimum combined price in lev.st format with exactly two fractional digits.
Constraints
Each distance is between 100 and 100000 metres inclusive; 100 stotinki = 1 lev.
Worked example
First official statement sample.
Input
1020 3005
Output
5.35
Solution analysis
- Use integer stotinki for all prices. Compare the distance in metres with each tariff boundary; the number of whole kilometres is metres / 1000 with integer division.
- For each delivery compute both courier prices using its tariff bracket and choose the smaller. Since each delivery can use either courier independently, add these two minima.
- For 1020 m, courier 2 costs 90 + 90 × 1 = 180 stotinki. For 3005 m it costs 100 + 85 × 3 = 355 stotinki. Both beat courier 1, giving 535 stotinki, printed as 5.35.
Why it works
Each computed price follows the applicable bracket and whole-kilometre charge. Any combined choice costs at least the minimum available price for each delivery. Choosing those two minima attains their sum, proving optimality.
Watch out. Use actual metres for bracket selection, but completed whole kilometres for the charge. Do not round up kilometres or use floating-point currency.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each computed price follows the applicable bracket and whole-kilometre charge. Any
// combined choice costs at least the minimum available price for each delivery.
#include<algorithm>
#include<iomanip>
#include<iostream>
using namespace std;
int cheapest(int metres){
int km=metres/1000;
int first;
if(metres<=5000){
first=400;
}
else if(metres<=10000){
first=700;
}
else if(metres<=20000){
first=1200;
}
else if(metres<=30000){
first=1700;
}
else{
first=57*km;
}
int second;
if(metres<=2000){
second=90+90*km;
}
else if(metres<=5000){
second=100+85*km;
}
else if(metres<=20000){
second=125+80*km;
}
else if(metres<=40000){
second=325+70*km;
}
else{
second=925+55*km;
}
return min(first,second);
}
int main(){
int a,b;
cin>>a>>b;
int total=cheapest(a)+cheapest(b);
cout<<total/100<<'.'<<setfill('0')<<setw(2)<<total%100<<'\n';
}