## Intuition The problem involves a student trying to minimize the time taken to reach the university by choosing the optimal bus stop to disembark. The bus travels along the x-axis, and the student must then walk to the university from the chosen bus stop. The goal is to minimize the total travel time, which is the sum of the time taken by the bus to reach a bus stop and the time taken by the student to walk from that bus stop to the university. ## Approach 1. **Input Parsing:** Read the number of bus stops `n`, the bus speed `vb`, and the student's walking speed `vs`. Then, read the coordinates of the bus stops and the university. 2. **Travel Time Calculation:** For each bus stop, calculate: - The time taken by the bus to reach the bus stop `i`: \( \text{time\_bus} = \frac{x_i}{v_b} \). - The Euclidean distance from the bus stop `i` to the university: \( \text{distance\_walk} = \sqrt{(x_i - x_u)^2 + y_u^2} \). - The time taken by the student to walk from the bus stop `i` to the university: \( \text{time\_walk} = \frac{\text{distance\_walk}}{v_s} \). 3. **Total Time Calculation:** Compute the total time for each bus stop as the sum of the bus travel time and the walking time. 4. **Optimal Bus Stop Selection:** Track the minimum total time and select the bus stop with the smallest index in case of ties. 5. **Output:** Print the index of the optimal bus stop (1-based index). ## Complexity - **Time Complexity:** \( O(n) \) because we iterate through each bus stop once to calculate the total travel time. - **Space Complexity:** \( O(1) \) as we only use a constant amount of extra space. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, vb, vs; cin >> n >> vb >> vs; vector x(n); for (int i = 0; i < n; ++i) { cin >> x[i]; } int xu, yu; cin >> xu >> yu; double min_time = DBL_MAX; int best_stop = -1; for (int i = 1; i < n; ++i) { double time_bus = static_cast(x[i]) / vb; double distance_walk = sqrt(pow(x[i] - xu, 2) + pow(yu, 2)); double time_walk = distance_walk / vs; double total_time = time_bus + time_walk; if (total_time < min_time || (abs(total_time - min_time) < 1e-9 && x[i] < x[best_stop])) { min_time = total_time; best_stop = i; } } cout << best_stop + 1 << '\n'; // Convert to 1-based index return 0; } ``` This solution efficiently calculates the optimal bus stop by iterating through each possible stop, computing the total travel time, and selecting the stop that minimizes this time. The use of `sqrt` and `pow` functions ensures accurate computation of Euclidean distances.

Running Student

Problem Details