2552:Assistance Required

keyword

シミュレーション　C++

概要

人々に2,3,...と番号が割り振られる。まず、番号2の人は仕事を免除され、それ以降の人は2ごとに仕事を割り振られて列から取り除かれる。次に番号3の人は…、番号5の人は…となる。仕事を免除される番号をlucky numberという。n(<3000)番目のlucky numberを求める問題。
愚直にシミュレートしてみると計算量がちょっと怪しい。実際に3000番目のlucky numberを手元で計算すると40000弱で、これでもちょっと際どいけどとりあえず投げてみる(駄目だったときは埋め込みすればよいので)。割と余裕でAC。

#define N 34000

int main(){
    int i, j, skip, cnt=0, n;
    bool ns[N];
    REP(i,N) ns[i] = true;
    int ans[3000];
    for(i=2;cnt<3000;i++){
        if(ns[i]){
            ans[cnt++] = i;
            skip = 0;
            for(j=i+1;j<N;j++){
                if(ns[j]){
                    skip++;
                    if(skip==i){
                        ns[j] = false;
                        skip = 0;
                    }
                }
            }
        }
    }
    while(scanf("%d",&n)){
        if(!n) break;
        printf("%d\n",ans[n-1]);
    }

    return 0;
}