joseph.txt

normal template for acm/ICPC

// Joseph's Problem
// input: n,m		-- the number of persons, the inteval between persons
// output:		-- return the reference of last person

int josephus0(int n, int m)
{
	if (n == 2) return (m%2) ? 2 : 1;
	int v = (m+josephus0(n-1,m)) % n;
	if (v == 0) v = n;
	return v;
}
int josephus(int n, int m)
{
	if (m == 1) return n;
	if (n == 1) return 1;
	if (m >=n) return josephus0(n,m);
	int l = (n/m)*m;
	int j = josephus(n - (n/m), m);
	if (j <= n-l) return l+j;
	j -= n-l;
	int t = (j/(m-1))*m;
	if ((j % (m-1)) == 0) return t-1;
	return t + (j % (m-1));
}