Where Was the Ball?
National Olympiad — Regional round (2020 season)
Submission name: ball.cpp
Problem summary
Three cup positions are numbered 0,1,2 from left to right. On odd-numbered moves, cups at positions 0 and 1 swap; on even-numbered moves, positions 1 and 2 swap. After n moves the ball is at position x. Determine its initial position.
Input
n, followed by x.
Output
The ball’s initial position, one of 0,1,2.
Constraints
1 ≤ n ≤ 1000000000000000000; 0 ≤ x ≤ 2.
Worked example
An independently prepared example for this explanation.
Input
4 2
Output
1
Solution analysis
- Two consecutive swaps cycle all three cup positions. Repeating this pair three times restores every cup, so the complete process repeats after six moves. Reduce n modulo 6.
- To recover the initial position, undo the remaining moves in reverse order. A swap is its own inverse: on an odd move exchange 0 and 1; on an even move exchange 1 and 2. If the ball is outside that pair, leave its position unchanged.
- For n=4 and final position 2, undo move 4 to obtain 1, move 3 to obtain 0, move 2 leaves 0 unchanged, and move 1 gives 1. Therefore the initial position was 1.
Why it works
The composition of one odd and one even move is a three-cycle, whose third power is the identity. Six moves therefore restore all positions, allowing reduction modulo six without changing the final arrangement. Applying the inverse swaps in reverse order exactly reverses that arrangement and recovers the initial ball position.
Watch out. Undo moves from last to first, preserving their original odd/even indices. A multiple of six requires no remaining swaps.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
long long n;
int position;
cin >> n >> position;
// Three pairs of alternating swaps restore all cup positions.
int remaining = static_cast<int>(n % 6);
for (int move = remaining; move >= 1; --move) {
int left = move % 2 == 1 ? 0 : 1;
int right = left + 1;
if (position == left) {
position = right;
} else if (position == right) {
position = left;
}
}
cout << position << '\n';
}