From : Rosetta
Josephus problem is a math puzzle with a grim description: n prisoners are standing on a circle, sequentially numbered from 0 to n − 1.
An executioner walks along the circle, starting from prisoner 0, removing every k-th prisoner and killing him.
As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed.
For example, if there are n = 5 prisoners and k = 2, the order the prisoners are killed in (let’s call it the “killing sequence”) will be 1, 3, 0, and 4, and the survivor will be #2.
Task Given any n,k > 0, find out which prisoner will be the final survivor. In one such incident, there were 41 prisoners and every 3rd prisoner was being killed (k = 3). Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale. Which number was he?
How To solve ?
There are n people in a circle, and people counts from 1 to k, and the person who count k will be eliminated. And we keep this process until there is only 1 person left in the circle.
Let’s first number position of these n people: 0, 1, 2, …, n-1. You notice that we change number from [1,2…n] to [0,1,…n-1], this is because of module operation. Likewise, people will now count from 0 to k-1, and the person who count k-1 will be eliminated.
The first person to be eliminated is in position (k-1)%n. After the first person has been eliminated, the circle now has only n-1 people left. One key discovery is that the last person who is finally eliminated(we call him lucky guy) is the same one to be eliminated in n-1 people circle!
Now we begin eliminate the second person:
Since (k-1)%n is the position that the first person got eliminated, then k%n must be the 0-th position for this round.
So we can number accordingly in the following table:
Position in first round ———-Position in second round
k%n ——————————— 0
k%n+1 ——————————- 1
k%n+2 ——————————- 2
….
Let’s assume the lucky guy in the first round in position: f(n, k).
Then the same lucky guy in the second round in position: f(n-1, k)
So, based on the table, we know the lucky guy in second round who is in position f(n-1, k), must be in position k%n+f(n-1,k) in the first round.
Position in first round ———-Position in second round
k%n ———————————- 0
k%n+1 ——————————– 1
k%n+2 ——————————– 2
…
k%n+f(n-1,k) ——————- f(n-1,k)
So, we know f(n,k) = k%n + f(n-1,k), to avoid over the range, we make it f(n,k) = (k%n + f(n-1,k)) % n = (k + f(n-1,k)) %n
Base Case : f(1,k) = 0;
Courtesy : Billionaire
Special Case :
k = 2,
We explicitly solve the problem when every 2nd person will be killed, i.e. k=2. We express the solution recursively. Let f(n) denote the position of the survivor when there are initially n people (and k=2). The first time around the circle, all of the even-numbered people die. The second time around the circle, the new 2nd person dies, then the new 4th person, etc.; it’s as though there were no first time around the circle.
If the initial number of people was even, then the person in position x during the second time around the circle was originally in position 2x – 1 (for every choice of x). Let n=2j. The person at f(j) who will now survive was originally in position 2f(j) – 1. This gives us the recurrence
f(2j)=2f(j)-1 ;.
If the initial number of people was odd, then we think of person 1 as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc. In this case, the person in position x was originally in position 2x+1. This gives us the recurrence
f(2j+1)=2f(j)+1 ;.
Problem : Problem
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LL long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define db(x) cout << #x << " -> " << x << endl;
#define DI(n) int n;sc(n)
#define DII(a,b) int a,b;sc(a);sc(b)
#define DIII(a,b,c) int a,b,c;sc(a);sc(b);sc(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void sc(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
template <class T> inline T bigmod(T p,T e,T M){LL ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return (T)ret;}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
const int N = 2005;
char st[10];
int calc(int n)
{
if(n==1) return 1;
if(n%2==0) return 2*calc(n/2) - 1;
else return 2 * calc(n/2) + 1;
}
int main()
{
while(1){
scanf("%s",st);
int n = (st[0] -'0') * 10 + st[1]-'0';
int p = st[3] -'0';
for(int i = 0; i<p;i++ ) n*=10;
if(n==0) break;
cout<< calc(n) << endl;
}
}
Here Problem List
1. Musical Chairs
2. WTK
3. King</a
4. UVA-10774
as the set of points `P` such that:
). 
to the circle formula and manipulate to get:
Code for Fun 