遅れて参加したけど、ギリギリ全完出来て良かった。
http://yukicoder.me/problems/no/438
問題
整数X,Y,Zが与えられる。
以下の4種類の命令からなるスタックマシンにおいて、10000回以下の命令でスタックの最上位をZに出来るか判定せよ。
- スタック最上位にXを積む
- スタック最上位にYを積む
- スタック最上位の2つの値を抜き出し、その和をまた最上位に積む
- スタック最上位の2つの値を抜き出し、最上位から1つ目のものから2つ目のものを引いた値をまた最上位に積む
解法
まずコーナーケースを片付けておく。
- Z==0の場合、Xを2回積んで差を取ればよい。
- X,Yのうち片方だけ使えばいい場合、すなわちZがXやYの倍数の場合、その数だけXやYを積んで和を取る。命令数が10000を超えないかは要チェック。
X*a+Y*b=Zを満たす整数a,bを求めよう。
命令長の上限が10000なので、|a|や|b|の上限は10000である。(正確には加減算も必要なので|a|+|b|は5000以下)
そのためaを-10000~10000総当たりし、対応するbが存在するか求めてみる。
存在する場合、2*(|a|+|b|)-1個の命令でZを作れるので、それが10000以下なら解が存在する。
- aもbも正なら、Xをa個、Yをb個積んで(a+b-1)回和を取ればよい。
- aが正でbが負なら、Yをb個積んで(b-1)回和を取り、Xをa個積んで(a-1)回和を取り、最後のその差を取る。
- aが負でbが正なら、Xをa個積んで(a-1)回和を取り、Yをb個積んで(b-1)回和を取り、最後のその差を取る。
ll X,Y,Z; void solve() { int i,j,k,l,r,x,y; string s; cin>>X>>Y>>Z; if(Z==0) return _P("ccW\n"); if(X==0 && Y==0) return _P("mourennaihasimasenn\n"); if(Y && Z%Y==0 && 2*(Z/Y)-1<=10000) { x = Z/Y; cout<<string(x,'w')<<string(x-1,'C')<<endl; return; } if(X && Z%X==0 && 2*(Z/X)-1<=10000) { x = Z/X; cout<<string(x,'c')<<string(x-1,'C')<<endl; return; } if(X==0 || Y==0) return _P("mourennaihasimasenn\n"); for(i=-10000;i<=10000;i++) { ll B=Z-X*i; if(B%Y) continue; ll C=B/Y; if((abs(i)+abs(C))*2-1>10000) continue; if(i>0 && C>0) { cout<<string(i,'c')<<string(C,'w')<<string(i+C-1,'C')<<endl; return; } else if(i<0) { cout<<string(abs(i),'c')<<string(abs(i)-1,'C')<<string(C,'w')<<string(abs(C)-1,'C')<<"W"<<endl; return; } else if(C<0) { cout<<string(abs(C),'w')<<string(abs(C)-1,'C')<<string(abs(i),'c')<<string(abs(i)-1,'C')<<"W"<<endl; return; } } _P("mourennaihasimasenn\n"); }
まとめ
最初互除法のコードを書いてしまった。