Oncoming Trains
National Olympiad — National round (2010 season)
Submission name: trains.cpp
Problem summary
For each of N city pairs, trains leave both endpoints every whole hour. A journey takes an integer number of hours. Count all oncoming trains met during a journey, including encounters at either station, and report the maximum over the city pairs.
Input
N followed by N positive integer journey durations in hours.
Output
The largest number of oncoming trains met.
Constraints
1 ≤ N < 20. Journey durations are positive integers; no numeric upper bound is stated.
Worked example
An independently prepared example for this explanation.
Input
5 3 4 7 6 1
Output
15
Solution analysis
- Take departure time as 0 and journey duration as t. An oncoming train departing at hour s overlaps this journey exactly when −t ≤ s ≤ t.
- There are 2t + 1 integer hours in this inclusive interval. This count grows with t, so find the largest supplied duration and apply the formula.
- The sample maximum duration is 7 hours. Departures from −7 through 7 contribute 15 trains, including those encountered at the start and finish stations.
Why it works
An oncoming train occupies the line during [s, s + t]. It meets our train during [0, t] exactly when these intervals overlap, equivalent to −t ≤ s ≤ t. Counting those hourly departures gives 2t + 1, and maximizing over all durations gives the requested maximum.
Watch out. Include station encounters at both ends, giving +1. Use 64-bit arithmetic for durations and counts.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
long long longest = 0;
for (int i = 0; i < n; i++) {
long long duration;
cin >> duration;
longest = max(longest, duration);
}
// Hourly oncoming departures range inclusively from -t through t.
cout << 2 * longest + 1 << '\n';
}