OJ Board

Code: Select all

/* Returns zero-based position of the survivor among n people, with elimination
   starting from person 0, and step prime[p] */
int survivor(int n, int p)
{
        int m, k;

        if (n <= 1)
                return 0;               /* one person left, he's the only survivor */

        m = (prime[p] - 1) % n;         /* who's leaving now */
        k = survivor(n - 1, p + 1);     /* the final survivor's position, relative to m */

        /*
         *  Now we need to map the final survivor's position back into the old
         *  indexing system. Here's an example for case n=9, m=3:
         *
         *          0 1 2 3 4 5 6 7 8  -- initial indexing
         *                x            -- person m=3 gets eliminated
         *  k=      5 6 7 . 0 1 2 3 4  -- what will be returned by the recursive call
         *  result: 0 1 2 . 4 5 6 7 8  -- back to the old indexing
         */ 

        if (k < (n - m - 1))
                return (k + m + 1);
        else
                return (k - (n - m - 1));
}

Code: Select all

int survivor(int n)
{
	int i, s;

	for (s = 0, i = 1; i <= n; i++)
		s = (s + prime[n - i]) % i;      /* assumes prime[0] = 2, ...*/

	return (s + 1);
}

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>

#define MAX 3502
#define M 40000

long prime[MAX];
char composite[M];

void seive()//Generate prime number up to 40000
{
	unsigned long i,j,k;
	memset(composite,'0',sizeof(composite));
	composite[1] = '1';

	int end = sqrt(MAX);
	for(i = 3;i<=end;i+=2)
	{
		if(composite[i]=='0')
		{
			k = M/i;
			for(j = i;j<=k;j+=2)
				composite[i*j] = '1';
		}
	}
	prime[0] = 2;
	for(i = 3,j = 1;i<MAX;i+=2)
		if(composite[i]=='0')
			prime[j++] = i;
}

void main()
{
	unsigned long i,j,k,count,n,test,J[MAX];
	char table[MAX];

	seive();
	n = 1;
	while(n<MAX)//for every numner find the last person
	{

		memset(table,'1',n+1);
		count = k = i = test = 0;
		while(count<n-1)
		{

			if(i>=n)
				i = 0;
			if(table[i]=='1')
			{
					test++;
			}
			if(test==prime[k])
			{
				table[i] = '0';
				count++;
				k++;
				test = 0;
			}
			i++;
		}
		for(i = 0;i<n;i++)
			if(table[i]=='1')
				break;
		J[n] = i+1;
		n++;
	}
	while(scanf("%lu",&n)!=EOF)
	{
		if(!n)
			break;
		printf("%lu\n",J[n]);
	}
}

Code: Select all

#include<stdio.h>
#include<math.h>
#include<vector>

using namespace std;
int prime[4200];

void sieve(int L,int U) 
	{
	int i,j,d;
	d=U-L+1; 
	bool *flag=new bool[d+1];
	for (i=(L%2!=0);i<d;i+=2) flag[i]=false;
	for (i=3;i<=sqrt(U);i+=2) 
		{
		if(i>L && !flag[i-L]) continue;
		j=L/i*i; 
		if (j<L) j+=i;
		if (j==i) j+=i; 
		for (j-=L;j<d;j+=i) flag[j]=false;
		}
	int n=0;
	if(L<=1) flag[1-L]=false;
	if(L<=2) flag[2-L]=true;
	for (i=0;i<d;i++) 
		{
		if (flag[i]) 
			{
			prime[n]=L+i;
			n++;
			}
		}
	}

int main()
{
sieve(1,33000);
int number;
while(scanf("%d",&number)==1 && number>0 && number<=3501)
	{
	if(number==2) 
		{
		printf("1\n");
		continue;
		}
	vector<int> v;
	int num=0,i;
	for(i=1;i<=number;i++)
		v.push_back(i);
	vector<int>::iterator k;
	k=v.begin();
	while(num<number-1)
		{
		i=prime[num];	
		i=i%v.size();
		k=k+i-1;
		if(i==0) v.erase(k);
		else if(k<v.end()) v.erase(k);
		else 
			{
			i=k-v.end();
			k=v.begin()+i;
			v.erase(k);
			}
		++num;
		}	
		printf("%d\n",*v.begin());
		v.empty();
	}
return 0;
}

Code: Select all

#include<stdio.h>
#include<math.h>
#include<vector>

using namespace std;
int prime[4200];

void sieve(int L,int U) 
	{
	int i,j,d;
	d=U-L+1; 
	bool *flag=new bool[d+1];
	for (i=(L%2!=0);i<d;i+=2) flag[i]=false;
	for (i=3;i<=sqrt(U);i+=2) 
		{
		if(i>L && !flag[i-L]) continue;
		j=L/i*i; 
		if (j<L) j+=i;
		if (j==i) j+=i; 
		for (j-=L;j<d;j+=i) flag[j]=false;
		}
	int n=0;
	if(L<=1) flag[1-L]=false;
	if(L<=2) flag[2-L]=true;
	for (i=0;i<d;i++) 
		{
		if (flag[i]) 
			{
			prime[n]=L+i;
			n++;
			}
		}
	}

int main()
{
sieve(1,33000);
int number;
vector<unsigned int> v;
while(scanf("%d",&number)==1 && number>0 && number<=3501)
	{
	int num=0,i;
	for(i=1;i<=number;i++)
		v.push_back(i);
	int	k=0;
	while(num<number-1)
		{
		i=prime[num];	
		if(i>number) i=i%(number-num);
		k=(k+i-1)%(number-num);
		v.erase(v.begin()+k);
		++num;
		}	
		printf("%d\n",v[0]);
		v.clear();
	}
return 0;
}

Code: Select all

#include<stdio.h>
#include<math.h>
#include<vector>

using namespace std;
int prime[4200];

void sieve(int L,int U) 
	{
	int i,j,d;
	d=U-L+1; 
	bool *flag=new bool[d+1];
	for (i=(L%2!=0);i<d;i+=2) flag[i]=false;
	for (i=3;i<=sqrt(U);i+=2) 
		{
		if(i>L && !flag[i-L]) continue;
		j=L/i*i; 
		if (j<L) j+=i;
		if (j==i) j+=i; 
		for (j-=L;j<d;j+=i) flag[j]=false;
		}
	int n=0;
	if(L<=1) flag[1-L]=false;
	if(L<=2) flag[2-L]=true;
	for (i=0;i<d;i++) 
		{
		if (flag[i]) 
			{
			prime[n]=L+i;
			n++;
			}
		}
	}

int main()
{
sieve(1,33000);
int number;
vector<int> v;
while(scanf("%d",&number)==1 && number>0 && number<=3501)
	{
	int num=0,i;
	for(i=1;i<=number;i++)
		v.push_back(i);
	int	k=0;
	while(num<number-1)
		{
		i=prime[num];	
		if(i>number) i=i%v.size();
		if(i==0 && k==0) k=v.size()-1;
		else k=(k+i-1)%v.size();
		v.erase(v.begin()+k);
		++num;
		}	
		printf("%d\n",v[0]);
		v.clear();
		}
return 0;
}

Code: Select all

$ g++ -o p p.cc
$ (seq 1 3501; echo 0) | ./p | uniq -c
      2 1
   3499 3
$