Bobi’s Hiking Trail
National Olympiad — Municipal round (2019 season)
Submission name: turist.cpp
Problem summary
Choose one of up to three hiking trails. Prefer the smallest supplied elevation-difference value l. If those values tie, prefer the shorter distance d. Report the chosen trail’s input position and its l value.
Source clarification. The PDF specifies smaller l, then shorter distance, and supplies no further rule for identical trails. The code chooses the first such trail. The PDF also calls both inputs integers before explicitly defining d as decimal; d is handled as decimal.
Input
n, followed by n pairs d and l. Distance d is decimal with at most three fractional digits; l is integer.
Output
The chosen 1-based trail number, then its l value on the next line.
Constraints
1 ≤ n ≤ 3; 1 ≤ d ≤ 150; 0 ≤ l ≤ 100000.
Worked example
An independently prepared example for this explanation.
Input
1 2.5 800
Output
1 800
Solution analysis
- The comparison uses the supplied l value directly. First minimize l, then distance. Do not divide the elevation difference by the distance; the statement defines its preference using the given value.
- Read the decimal distance as a string and convert it to integer meters by padding the fractional part to three digits. Comparing these integers avoids floating-point concerns and preserves every allowed distance exactly.
- In the third sample, trails 2 and 3 both have l=600, beating trail 1 with l=800. Their distances are 7 and 3 kilometers, so trail 3 wins and the output is 3 followed by 600. For completely identical criteria, the code retains the first trail.
Why it works
After each trail, the stored candidate has the smallest pair (l,d) in lexicographic order among those read. A new trail replaces it exactly when this pair improves, preserving the invariant. After all input, the candidate satisfies both stated priorities.
Watch out. Distance may contain a decimal point despite the PDF calling the input numbers integers. Compare l first, and output l rather than the distance.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
long long distanceInMeters(string text) {
size_t point = text.find('.');
string whole = point == string::npos ? text : text.substr(0, point);
string fraction = point == string::npos ? "" : text.substr(point + 1);
// Pad to thousandths of a kilometer for exact integer comparisons.
while (fraction.size() < 3) {
fraction += '0';
}
return stoll(whole) * 1000 + stoll(fraction);
}
int main() {
int n;
cin >> n;
int bestIndex = 0;
int bestSlope = 0;
long long bestDistance = 0;
for (int i = 1; i <= n; ++i) {
string text;
int slope;
cin >> text >> slope;
long long distance = distanceInMeters(text);
if (i == 1 || slope < bestSlope || (slope == bestSlope && distance < bestDistance)) {
bestIndex = i;
bestSlope = slope;
bestDistance = distance;
}
}
cout << bestIndex << '\n' << bestSlope << '\n';
}