Jumps Around a Circle
National Olympiad — Municipal round (2022 season)
Submission name: circle.cpp
Problem summary
Positions 1 to N lie clockwise around a circle. Start at position 1 and make K jumps, each moving clockwise across D arcs. Sum the position labels visited, including the starting position and counting repeated visits again.
Input
Three integers N D K.
Output
The sum of the K+1 visited labels.
Constraints
0 < N,D,K < 1000.
Worked example
An independently prepared example for this explanation.
Input
5 3 4
Output
15
Solution analysis
- Store the current position as a zero-based index p. One jump updates p = (p+D) mod N, which works even when D exceeds N.
- Initialize the sum to 1 for the starting visit. After each of K jumps, add p+1, the corresponding one-based label.
- For N=5, D=3, K=4, the visited labels are 1,4,2,5,3. Their sum is 15. If a jump returns to a previously visited label, it still contributes another visit.
Why it works
Modulo N wraps the clockwise displacement exactly around the circle. Each update therefore finds the correct next landing label. The initial addition and one addition per jump count exactly all required visits.
Watch out. Include the initial 1. Sum landing positions, not every label crossed during a jump.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int n, distance, jumps;
cin >> n >> distance >> jumps;
int position = 0;
int sum = 1;
for (int jump = 0; jump < jumps; jump++) {
// A zero-based index makes wraparound a single remainder.
position = (position + distance) % n;
sum += position + 1;
}
cout << sum << '\n';
}