cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2012 · MediumTwo pointers

Nearest Unvisited House

Autumn Tournament (2012)

Submission name: postman.cpp

Solve in Editor →

Problem summary

Houses 1 through N lie in order on a straight street, with given positive distances between neighbours. A postman starts at house K. After visiting a house, he moves to the nearest unvisited house; ties are resolved toward the smaller house number. Find his total travelled distance.

Input

N K, followed by N-1 distances between consecutive houses.

Output

The total distance travelled until all houses have been visited.

Constraints

1 ≤ N ≤ 100000; 1 ≤ K ≤ N; distances are positive integers and the final answer fits a signed int.

Worked example

Original statement sample, with whitespace restored where PDF extraction merges adjacent numbers.

Input

5 4
90
20
10
50

Output

280

Solution analysis

  1. Build prefix positions: position[1]=0 and position[i+1]=position[i]+distance[i]. Distances between any two houses are then differences of their positions.
  2. At every stage the visited houses form an interval [left,right]. The nearest unvisited house can only be left-1 or right+1: every other unvisited house is farther beyond one of these. Compare their distances from the current house, choosing the left candidate on equality. Extend the visited interval by that chosen house.
  3. For the sample the positions are 0,90,110,120,170 and the start is house 4. The chosen houses are 3,2,5,1, with travel distances 10,20,80,170. Their sum is 280.

Why it works

Initially the visited interval contains only K. On a line with positive gaps, any unvisited house beyond a frontier is farther from the current position than that frontier. Choosing the closer available frontier therefore follows the required rule, and adding it preserves the interval invariant. Induction covers all visits.

Complexity: O(N) time for prefix positions and N-1 visits; O(N) space for positions. Each iteration visits exactly one new house.

Watch out. Compare distances from the current house, not merely the gaps at the two interval ends. On a tie choose the left frontier. Handle exhausted left or right sides and N=1. long long keeps intermediate arithmetic safe.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<limits>
using namespace std;
int main(){
    int n;
    int start;
    cin>>n>>start;
    vector<long long>position(n+1,0);
    for(int i=2;i<=n;++i){
        long long gap;
        cin>>gap;
        position[i]=position[i-1]+gap;
    }
    int left=start;
    int right=start;
    int current=start;
    long long total=0;
    while(left>1||right<n){
        long long leftDistance=numeric_limits<long long>::max();
        long long rightDistance=numeric_limits<long long>::max();
        if(left>1){
            leftDistance=position[current]-position[left-1];
        }
        if(right<n){
            rightDistance=position[right+1]-position[current];
        }
        // Equality must choose the smaller house number.
        if(leftDistance<=rightDistance){
            total+=leftDistance;
            current=--left;
        }
        else{
            total+=rightDistance;
            current=++right;
        }
    }
    cout<<total<<'\n';
}

Source: Arena Olimpiici ↗