SRM337Div2

250

class Palindromize2 {
public:
  string minChanges(string s) {
    for(int i=0; i<s.size(); ++i){
      s[i] = min( s[i], s[(int)s.size()-1-i] );
    }
    return s;
  }
};

500

class CardStraights {
public:
  int longestStraight(vector <int> c) {
    int z = count( c.begin(), c.end(), 0 );
    sort( c.begin(), c.end() );

    for(int i=0; i<c.size(); ++i){
      if( c[i] == 0 ) c.erase( c.begin() + i-- );
    }
    for(int i=0; i+1<c.size(); ++i){
      if( c[i] == c[i+1] ) c.erase( c.begin() + i-- );
    }

    int mx = (bool)c.size() + z;
    for(int i=0; i<c.size(); ++i){
      for(int j=i+1; j<c.size(); ++j){
        int diff = 0;
        for(int k=i; k+1<=j; ++k){
          diff += c[k+1] - c[k] - 1;
        }
        if( diff <= z ){
          mx = max(mx, c[j] - c[i] + (z - diff) + 1);
        }
      }
    }

    return mx;
  }
};

1100

lli f[20+1];

lli C(string s)
{
  lli n = f[ s.size() ];
  for(char c='a'; c<='z'; ++c){
    n /= f[ count(s.begin(), s.end(), c) ];
  }
  return n;
}

string rec(const string s, lli sum, lli I)
{
  for(int i=0; i<s.size(); ++i){
    if(i && s[i-1] == s[i])continue;
    string t = s;
    t.erase( t.begin() + i );
    lli n = C(t);
    if(I < sum + n){
      return s[i] + rec(t, sum, I);
    }
    sum += n;
  }
  return "";
}

class AnagramList {
public:
  string getAnagram(string s, int I) {
    sort( ALL(s) );
    f[0] = 1;
    for(int i=1; i<=20; ++i){
      f[i] = f[i-1] * (lli)i;
    }
    return C(s) < I ? "" : rec(s, 0, I);
  }
};