Choose a Josephus Circle Size
National Olympiad — National round (2024 season)
Submission name: game.cpp
Problem summary
Choose n friends from m to join the player. Starting at person 1, repeatedly eliminate the next surviving person around the circle. Find all n≤m leaving player p as winner.
Input
m p.
Output
Number of valid invitation counts, followed by their increasing list if nonempty.
Constraints
1≤p≤m+1≤10^9. The official released solution includes zero invitations when p=1.
Worked example
Input and output for the worked example discussed below.
Input
12 7
Output
2 6 10
Solution analysis
- For T=n+1 total players, the every-second elimination winner is J(T)=2(T−P)+1, where P is the greatest power of two not exceeding T. Winners restart at 1 at each power of two and then increase by two.
- Even p cannot win. For odd p, let q=(p−1)/2. The equation forces T=P+q. Enumerate powers P and require q<P and T≤m+1, then output T−1 friends.
- For m=12,p=7, q=3. Powers 4 and 8 give 7 and 11 total players, hence 6 and 10 friends. For p=1, include n=0: a solo player wins, following the official reference convention.
Why it works
The Josephus recurrence gives the power-of-two winner formula. Its inverse requires T=P+q, while q<P is exactly P≤T<2P. Availability is T−1≤m. Thus precisely the valid counts are emitted, in increasing order.
Watch out. Use n+1 total players, not n. Do not stop at T≤m. Preserve the documented zero-invitation convention.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
long long friends;
long long desired;
cin>>friends>>desired;
vector<long long>answers;
if(desired%2==1){
long long offset=(desired-1)/2;
for(long long power=1;power<=friends+1;power*=2){
long long players=power+offset;
// This must be the greatest power of two not exceeding players.
if(offset<power&&players<=friends+1){
answers.push_back(players-1);
}
}
}
cout<<answers.size()<<'\n';
if(!answers.empty()){
for(int i=0;i<int(answers.size());i++){
if(i>0){
cout<<' ';
}
cout<<answers[i];
}
cout<<'\n';
}
}