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;
}