Fuel at Promotional Stations
National Olympiad — Municipal round (2025 season)
Submission name: fuel.cpp
Problem summary
A trip is N kilometers long. The car refuels at positions 0,K,2K,… strictly before the destination, buying enough for the next K kilometers or the remaining distance if shorter. At station X, fuel costs B per kilometer if the digit sum of X is divisible by Y; otherwise it costs A. Find the total bill.
Input
N K Y A B.
Output
The total fuel cost.
Constraints
1 ≤ N,K ≤ 1000; 1 ≤ Y ≤ 30; 1 ≤ B < A ≤ 10.
Worked example
An independently prepared example for this explanation.
Input
30 8 3 5 4
Output
136
Solution analysis
- The refueling stops are fixed by the statement, so there is no route optimization. Loop over multiples of K smaller than N.
- At a stop X, sum its decimal digits, select the promotional or standard rate, and multiply it by min(K,N−X). The digit sum of zero is zero, so the initial stop always qualifies for the promotion.
- The sample stops at 0,8,16,24. Rates are 4,5,5,4 and amounts are 8,8,8,6 kilometers. Their costs sum to 32+40+40+24=136.
Why it works
The loop visits exactly the required refueling positions. Each purchase covers precisely the distance until the next stop or the destination, so the purchases partition the trip. Applying each station’s stated rate and summing therefore gives the total bill.
Watch out. Do not buy fuel at the destination. The last purchase may be shorter than K, including when K>N. Position zero qualifies for every Y.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, k, y, standard, promotion;
cin >> n >> k >> y >> standard >> promotion;
int total = 0;
for (int position = 0; position < n; position += k) {
int value = position;
int digitSum = 0;
while (value > 0) {
digitSum += value % 10;
value /= 10;
}
// At position zero digitSum is zero, which qualifies for promotion.
int rate = digitSum % y == 0 ? promotion : standard;
total += min(k, n - position) * rate;
}
cout << total << '\n';
}