PKU : 2552 - Assistance Required
問題概要
http://poj.org/problem?id=2552
2,3,4,5,... の連続する番号があります.
はじめ, 1番目の数字を見ます. 2なので, 2個とばしで数字を消していきます.
次に, 2番目の数字を見ます. 先ほどの操作で残っている数字に対して, 3個とばしで数字を消していきます.
この操作を繰り返してできあがる数列で, n番目の数字を求めよ.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 //最初の数字 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 //2個とばしで消す 2 3 5 7 11 13 17 19 23 25 29 //3個とばしで消す 2 3 5 7 11 13 17 23 25 29 //5個とばしで消す
アルゴリズム
3000項目の数字はそんなに大きくないので, ただのシミュレートで解けてしまいます.
プログラム
int main(void){ vector<int> v; for(int i=2;i<=35000;i++){ v.push_back(i); } for(int i=0;i<v.size() && i<3000;i++){ vector<int> nv; for(int j=0;j<v.size();j++){ if(j <= i || (j-i) % v[i] != 0){ nv.push_back(v[j]); } } v = nv; } int n; while(cin>>n,n){ cout<<v[n-1]<<endl; } }