PKU 3629 Card Stacking
http://poj.org/problem?id=3629
bessieはn-1の友達とk(nの倍数)枚のカードを使ってカードゲームをしていた。
デッキにはm=k/n枚の"good"なカードがあり、k-m枚の"bad"なカードがある。
bessieがディーラーであり、彼女は全ての"good"なカードを自分が引けるようにしたい。
彼女の友人は彼女がチートをするかもしれないと疑って、彼女に次のようにカードを配るよう指示した。
1.最初に山札の一番上のカードを彼女の右の牛に配る。
2.そして配るたびに、次のp枚のカードを山札の一番下に送り、
3.全てのカードを順番に配っていく。
全ての"good"なカードをbessieが得るためにそのカードを山札のどこにおいておけばよいを答えるというような問題。
以前なぜかsetを使っていたせいでTLEしていた問題。
listにしてギリギリAC。
int ans[100000]; int anum; main(){ int n,k,p; cin>>n>>k>>p; list<int> app; rep(i,k)app.pb(i+1); list<int>::iterator iter=app.begin(); int sz=0; int mv=0; while(true){ //cout<<*siter<<endl; int t=*iter; iter=app.erase(iter); if(iter==app.end())iter=app.begin(); ++sz; if(sz%n==0)ans[anum++]=t; if(app.empty())break; rep(i,p){ ++iter; if(iter==app.end())iter=app.begin(); } } sort(ans,ans+anum); rep(i,anum)cout<<ans[i]<<endl; }