PKU 2116 Death to Binary?
http://poj.org/problem?id=2116
フィボナッチ進数的な数字が与えられる。
それらの和を連続して1を持たないようなフィボナッチ進数に直して出力しろというような問題。
450問目。
桁の大きい物で割り当て可能なものから貪欲に割り当てれば、連続して1を持たないように出来る。
入力として0がくるというパターンにはまってWAを出しました。
ll fib[100]; ll toll(const string&in){ ll ret=0; int sz=SZ(in); rep(i,sz){ if(in[sz-i-1]=='1')ret+=fib[i]; } return ret; } string tostr(ll in){ if(in==0)return "0"; int pos=0; while(fib[pos]<=in)++pos; string ret; while(pos){ --pos; if(in>=fib[pos])ret+='1',in-=fib[pos]; else ret+='0'; } return ret; } main(){ fib[0]=1; fib[1]=2; for(int i=2;i<50;i++){ fib[i]=fib[i-1]+fib[i-2]; } string a,b; while(cin>>a>>b){ string ans=tostr(toll(a)+toll(b)); a=tostr(toll(a)); b=tostr(toll(b)); cout<<" "; cout<<string(SZ(ans)-SZ(a),' ')<<a<<endl; cout<<"+ "; cout<<string(SZ(ans)-SZ(b),' ')<<b<<endl; cout<<" "<<string(SZ(ans),'-')<<endl; cout<<" "<<ans<<endl; cout<<endl; } }