Minimum Jumps over Rotten Planks
National Olympiad — Regional round (2022 season)
Submission name: skok.cpp
Problem summary
Move forward from A to B in jumps of one or two, avoiding nonadjacent rotten planks.
Input
A B, then N and N rotten positions.
Output
The minimum jump count.
Constraints
1≤A≤B≤10^18; 0≤N≤100000; endpoints safe; rotten positions distinct and nonadjacent.
Worked example
Input and output for the worked example discussed below.
Input
3 12 1 4
Output
5
Solution analysis
- A safe distance d takes ceil(d/2) jumps. A rotten plank x forces the crossing x−1→x+1, because no other permitted jump can pass it.
- Sort rotten positions. Reach x−1 optimally, add the crossing, and continue from x+1. Finish the final safe stretch after the last relevant rotten position.
- For3→12 with rotten4, jump3→5, then cover distance7 in four more jumps. Total5. No per-plank scan is needed even for10^18-sized coordinates.
Why it works
Every feasible route has the same mandatory rotten-plank crossings. Safe stretches independently require and attain ceil(distance/2), so summing their minima and crossings is globally optimal.
Complexity: O(NlogN) time and O(N) space.
Watch out. Use64-bit coordinates; ignore rotten positions outside the travelled interval; A=B needs zero jumps.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// Every feasible route has the same mandatory rotten-plank crossings.
int main(){
long long start,finish;
int n;
cin>>start>>finish>>n;
vector<long long>a(n);
for(long long&x:a){
cin>>x;
}
sort(a.begin(),a.end());
long long current=start,answer=0;
for(long long x:a){
if(x<=start||x>=finish){
continue;
}
answer+=(x-current)/2+1;
current=x+1;
}
answer+=(finish-current+1)/2;
cout<<answer<<'\n';
}