PKU 2552 Assistance Required
http://poj.org/problem?id=2552
2から順番に番号付けされて人が並んでいる。
ここから皿洗いをする人を選ぶために以下の操作を行ったときに、n番目の皿を洗わなくてもいい人の番号を答えるというような問題。
各操作のはじめに行列の先頭の人が皿を洗わなくてもいい人に入れられる。
その後、皿を洗わなくてもいい人が持っていた数字ごとに後ろの人は皿洗いに回される。
これを繰り返す。
最初素数の篩の問題かと思って、サンプルをろくに確認せずにWAを出しました。
シミュレーション。
vector<int> ans; main(){ vector<int> q; rep(i,34000)q.pb(i+2); rep(i,3000){ ans.pb(q[0]); vector<int> nq; for(int j=1;j<SZ(q);j++){ if(j%q[0]==0)continue; nq.pb(q[j]); } q=nq; } int n; while(cin>>n,n)cout<<ans[n-1]<<endl; }