PKU 2969 Divisibility by 15
http://poj.org/problem?id=2969
与えられた数字から15で割り切れる最大の数を作れというような問題。
場合分けがものすごく面倒くさい上に、1の位に5を持ってくるパターンで最大じゃないものを返していてそこでずっとハマってました。
int mod[3]; main(){ string in; cin>>in; int sum=0; int n5=0,n0=0; rep(i,SZ(in)){ sum+=in[i]-'0'; mod[(in[i]-'0')%3]++; if(in[i]=='5')n5++; if(in[i]=='0')n0++; } if((n5+n0)==0 || (sum%3==1 && mod[1]==0 && (mod[2]<2 || (n0==0 && mod[2]<3))) || (sum%3==2 && mod[1]<2 && (mod[2]==0 || (n0==0 && mod[2]<2)))){ cout<<"impossible"<<endl; return 0; } sort(ALL(in)); if(sum%3==1){ if(mod[1]){ rep(i,SZ(in)){ if((in[i]-'0')%3==1){ in.erase(i,1); break; } } }else{ if(in[0]=='0'){ rep(t,2)rep(i,SZ(in)) if((in[i]-'0')%3==2){ in.erase(i,1); break; } }else{ rep(t,2)rep(i,SZ(in)){ if((in[i]-'0')%3==2 && in[i]!='5'){ in.erase(i,1); break; } if(in[i]=='5' && n5>1){ --n5; in.erase(i,1); break; } } } } }else if(sum%3==2){ if(mod[2] && (n0 || mod[2]>1)){ if(in[0]=='0'){ rep(i,SZ(in)) if((in[i]-'0')%3==2){ in.erase(i,1); break; } }else{ rep(i,SZ(in)){ if((in[i]-'0')%3==2 && in[i]!='5'){ in.erase(i,1); break; } if(in[i]=='5' && n5>1){ --n5; in.erase(i,1); break; } } } }else if(mod[1]>1){ rep(t,2)rep(i,SZ(in)){ if((in[i]-'0')%3==1){ in.erase(i,1); break; } } }else for(;;); } if(SZ(in)==0){ cout<<"impossible"<<endl; return 0; } if(in[0]!='0'){ bool ok=false; rep(i,SZ(in)){ if(in[i]=='5'){ in="5"+in.substr(0,i)+in.substr(i+1); break; } } } reverse(ALL(in)); while(in[0]=='0' && SZ(in)>1)in=in.substr(1); cout<<in<<endl; }