Waiting for the Bus
National Olympiad — National round (2021 season)
Submission name: buses.cpp
Problem summary
P buses arrive at times X,2X,…,PX, each boarding up to N people in arrival order. T people arrive at times Y,2Y,…,TY; Chris is the last of them. A person arriving with a bus can board it. Determine Chris’s waiting time or report No if the buses cannot carry him.
Input
P T; X Y; then N, the capacity per bus.
Output
The waiting time in minutes, or No.
Constraints
0 < P,T,X,Y,N < 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
2 5 7 2 3
Output
4
Solution analysis
- Scan bus arrivals instead of every minute. At bus time b·X, min(T,floor(b·X/Y)) people have arrived in total. Subtract the number already boarded to get the queue.
- Board the smaller of the queue size and N. The first time the boarded total reaches T, Chris has boarded; subtract his arrival time T·Y from that bus time.
- In the sample, bus 1 at time 7 takes the first three people. Chris arrives at time 10, and bus 2 at time 14 takes him after the fourth person. His wait is 14−10 = 4 minutes.
Why it works
Before each bus, boarded counts exactly those served earlier. The arrival formula includes everyone present at that instant, so capacity-limited boarding gives the correct new total. Chris is last, hence he boards exactly when this total first reaches T. If it never does, no remaining bus can serve him.
Watch out. Use 64-bit products for bus and person times. Include a simultaneous person arrival before boarding. Output No with the specified capitalization.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long long buses, people, busInterval, personInterval, capacity;
cin >> buses >> people >> busInterval >> personInterval >> capacity;
long long boarded = 0;
for (long long bus = 1; bus <= buses; bus++) {
long long time = bus * busInterval;
// Integer division includes people arriving at this exact time.
long long arrived = min(people, time / personInterval);
boarded += min(capacity, arrived - boarded);
if (boarded == people) {
cout << time - people * personInterval << '\n';
return 0;
}
}
cout << "No\n";
}