UVA online 10015_Joseph's Cousin

coding cpp uvaonline

Well, this week took longer than usually, not because the problem was hard. Actually the problem was pretty similar to the one last week, but instead of just a single number, this problem uses prime number to remove people from the circle. The simulation is similar to last week, but i messed up the prime generation section of the code, which i had to redo and try again, after checking that all the 4200 primes are correct, this is the final code.


#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;

int p[4200];

int survivor(int n){
    queue arr;
    for(int i=1; i<n+1; i++) arr.push(i);          int rmv=0, c;     while(arr.size()>1){
        c = (p[n-arr.size()]-1)%arr.size();
        for(int i=0; i<c; i++){
            arr.push(arr.front()); arr.pop();
        }
        arr.pop();
    }
    
    return arr.front();
    
    // int i, s;
    // for(s=0, i=1; i<=n; i++){
        // s = (s + p[n - i]) % i;
    // }
    
    // return s+1;
}

int main(){
    int t, m, b, c=2, i=0;
    while(i<4200){
        while(true){
            if(c==2){ p[i] = 2; i++;}
            else{
                t = 0; m = int(pow(c, 0.5)+1); b = 1;
                
                while(t<i && p[t]<=m){
                    if(!(c%p[t])){ b=0; break; }
                    t++;
                }
                if(b){p[i]=c; c++; break;}
            }
            c++;
        }
        i++;
    }
    
    int n; scanf("%d", &n);
    while(n){
        printf("%d\n", survivor(n));
        scanf("%d", &n);
    }
    
    return 0;
}