PKU 3517 And Then There Was One
id:kyuridenamidaのところ(http://d.hatena.ne.jp/kyuridenamida/20110724/1311503122)にはシミュレーションでは間に合わないとか書いてありましたが間に合いました(漸化式とか知らない無知)
ただ、普通にシミュレーションするんじゃなくて多少工夫します。多少ですが
殺す場所を記録していって、今いる人の範囲内なら-1にしてころします
範囲外なら-1の人を実際に削除して、殺した場所のつじつまを合わせます
bool judge(int n){ return n==-1; } int seq[10001]; int main(){ int n,k,m; while(scanf("%d%d%d",&n,&k,&m)!=EOF && (n||k||m)){ REP(i,n) seq[i]=i+1; int begin=m-1,n2=n; REP(i,n-1){ seq[begin]=-1; begin+=k; if(begin>=n2){ begin-=n2; n2=remove_if(seq,seq+n2,judge)-seq; begin%=n2; } } REP(i,n2) if(seq[i]!=-1){ printf("%d\n",seq[i]); break; } } return 0; }
(非想定解を自慢げに書く自分ェ・・・)