
input:
3501
3500
3499
3498
3497
3496
3495
3400
3000
5
4
3
2
1
0
corresponding output:
2995
1543
1868
1090
1244
1694
2753
2482
1361
1
4
1
1
1
Moderator: Board moderators
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;
}
And FYI:A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point.
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;
}
and it was triggered because k==-1, which happened because at previous step k and i were zeroes, and -1 % whatever == -1.v.erase(v.begin()+k);
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
$
Your program outputs the correct answer in only 14 cases out of 3501 (i.e. the first two 1's are OK, and then there are 12 cases output for which happens to be 3).i check different type of input and output in UVa toolkit and my code and i have correct answer