Bus Passes
National Olympiad — Municipal round
Submission name: bus.cpp
Problem summary
Stops 1…K lie on one bus line. Ordinary travel costs one unit per adjacent pair. The whole line is partitioned into N consecutive routes whose neighboring endpoints coincide. A pass for a route costs less than its full length and permits travel within that route. Find the minimum cost from stop A to stop B. Routes may be listed in any order.
Input
N A B, then N triples p q s: route endpoints and pass price.
Output
The minimum total fare.
Constraints
1≤N≤100; A<B; K<5000.
Worked example
An independently prepared example for this explanation.
Input
2 3 9 1 5 3 5 10 2
Output
4
Solution analysis
- For each route, compute the length t of its overlap with [A,B].
- That portion can be paid with t ordinary tickets or the route’s pass, so contribute min(t,s).
- Sum independently over routes.
Why it works
Route interiors are disjoint and every traversed edge belongs to exactly one route. A pass for another route cannot cover it; choosing the cheaper of tickets and its own pass in each route is both necessary and achievable.
Watch out. A pass can be worthwhile even if only part of its route is travelled. Do not assume sorted input.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Route interiors are disjoint and every traversed edge belongs to exactly one route. A pass
// for another route cannot cover it; choosing the cheaper of tickets and its own pass in each route is
// both necessary and achievable.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n,a,b;
cin>>n>>a>>b;
int ans=0;
while(n--){
int p,q,s;
cin>>p>>q>>s;
int overlap=max(0,min(b,q)-max(a,p));
ans+=min(overlap,s);
}
cout<<ans<<'\n';
}