Reconstructing a Fortune Wheel
National Olympiad — Municipal round (2021 season)
Submission name: wheel.cpp
Problem summary
Reconstruct distinct letters on a rotating wheel from observed step counts and letters.
Input
N K, then K pairs S letter.
Output
Clockwise letters from the final pointer, ? for unknown sectors, or ! for contradictions.
Constraints
2≤N≤25; 1≤K≤100; 1≤S≤100.
Worked example
Input and output for the worked example discussed below.
Input
5 6 1 A 2 B 5 B 1 C 2 A 2 B
Output
B?A?C
Solution analysis
- Number sectors relative to the initial pointer. Add each step count modulo N to find the next observed sector; its letter is then fixed.
- Reject either two different letters at one sector or one letter at two sectors. Otherwise leave unobserved sectors as ?, since they can be assigned unused letters.
- The physical clockwise order reverses the pointer-index direction. In the sample, reading backwards from the final B gives B?A?C. A full N-step turn returns to the same sector.
Why it works
Cumulative steps uniquely fix relative observed positions. Consistent, nonrepeated fixed letters satisfy all observations, and unused letters can fill the remaining sectors. Reverse-index reading gives the requested physical order.
Complexity: O(K+N) time and O(N+26) space.
Watch out. Check both conflict types and reverse the output direction.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<array>
#include<algorithm>
using namespace std;
// Cumulative steps uniquely fix relative observed positions.
int main(){
int n,k;
cin>>n>>k;
string wheel(n,'?');
array<int,26>where;
where.fill(-1);
int position=0;
bool valid=true;
for(int i=0;i<k;i++){
int steps;
char letter;
cin>>steps>>letter;
position=(position+steps)%n;
int code=letter-'A';
if((wheel[position]!='?'&&wheel[position]!=letter)||
(where[code]!=-1&&where[code]!=position)){
valid=false;
}
wheel[position]=letter;
where[code]=position;
}
if(!valid){
cout<<"!\n";
return 0;
}
for(int i=0;i<n;i++){
cout<<wheel[(position-i+n)%n];
}
cout<<'\n';
}