UVA online 10015_Joseph’s Cousin

#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;
}

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.

Advertisements

UVA online 00305_Joseph

This is really similar to the one that I did last week, anyway, this problem is really quite a tedious one, because of the large answers for the questions. Well, the algorithm that I written was also greatly improved using the modulus function, which reduced the number of operations ran. The algorithm for the check is left in the solution for reference.

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

bool isValid(int k, int m){
    queue arr;

    for(int i=0; i<k; i++) arr.push(1);
    for(int i=0; i<k; i++) arr.push(0);          int rmv = 0;     while(arr.size()>k && !rmv){
        int n = (m-1)%arr.size();
        for(int i=0; i<n; i++){
            arr.push(arr.front()); arr.pop();
        }
        rmv = arr.front(); arr.pop();
    }

    return (arr.size()<=k && !rmv);
}

int main(){
    char line[1024]; gets(line);
    int k; sscanf(line, "%d", &k);
    int ans[]={2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881};

    while(k){
        // int m = k+1;
        // while(!isValid(k, m)) m++;

        printf("%d\n", ans[k-1]);
        gets(line); sscanf(line, "%d", &k);
    }
    return 0;
}