Refuelling Routes
National Olympiad — National round
Submission name: fuel.cpp
Problem summary
Travel from position 0 to K along a line, starting with a full tank. A full tank permits at most L distance; stopping at a station refills it. Count distinct increasing sequences of visited stations that reach K, modulo 1000000007. Skipping all stations is allowed when possible. Only routes of minimum travelled distance K count; the number of stops need not be minimum.
Input
N K L, then N strictly increasing station positions.
Output
The number of valid routes modulo 1000000007.
Constraints
1 ≤ N ≤ 1000000; 0 < A_i < K < 1000000000; 1 ≤ L ≤ 1000000000.
Worked example
An independently prepared example for this explanation.
Input
2 8 5 3 5
Output
3
Solution analysis
- Append the destination and prepend the start, whose route count is 1.
- dp[i] sums dp[j] over earlier positions within distance L. Maintain this sum with a moving left boundary; remove expired positions before computing dp[i].
Why it works
Every valid route has a unique penultimate stop within L. Conversely appending the current stop to every counted prefix creates exactly all valid routes. The window maintains precisely this predecessor sum.
Watch out. Do not minimize the stop count. Normalize modular subtraction.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k,L;
cin>>n>>k>>L;
vector<int>a(n+2),dp(n+2);
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[n+1]=k;
const int MOD=1000000007;
dp[0]=1;
long long sum=1;
int left=0;
for(int i=1;i<=n+1;i++){
while(a[i]-a[left]>L){
sum=(sum-dp[left]+MOD)%MOD;
left++;
}
dp[i]=sum; // Sum of all legal preceding stops.
sum=(sum+dp[i])%MOD;
}
cout<<dp[n+1]<<'\n';
}