SRM464 Div1 Easy

250
全部試す。
明らかに作れない場合、0が答えになりそうな場合は別処理。

class ColorfulStrings {
public:
  string getKth(int n, int k) {

    if( n == 1 && k <= 10 )return string("") + (char)('0' + k - 1);
    if( 10 <= n )return "";

    string s = "123456789";
    set<int> vis;
    priority_queue<string> q;

    do{
      string t = s.substr( 0, n );
      int m = atoi( t.c_str() );
      if( vis.count( m ) )continue;
      vis.insert( m );

      set<int> mul;
      bool flg = true;

      for(int i=0; i<t.size() && flg; ++i){
        for(int j=i; j<t.size() && flg; ++j){
          int m = 1;
          for(int k=i; k<=j; ++k){
            m *= t[k] - '0';
          }
          if( mul.count( m ) ) flg = false;
          mul.insert( m );
        }
      }
      if( !flg )continue;
      q.push( t );

    }while( next_permutation( s.begin(), s.end() ) );

    if( q.size() < k )return "";
    while( q.size() != k )q.pop();
    return q.top();
  }
};