SRM323Div2

250

class IrreducibleNumber {
public:
  int getIrreducible(vector <int> A) {
    set<int> s;
    for(int i=1; i<(1 << A.size()); ++i){
      int sum = 0;
      for(int j=0; j<A.size(); ++j){
        if( i & (1 << j) )sum += A[j];
      }
      s.insert( sum );
    }
    for(int i=1; ; ++i){
      if( s.count(i) == 0 ) return i;
    }
    return -1;
  }
}; 

500

 class RoadsAndFools {
public:
  string determineOrientation(int len, vector <int> f) {
    const string MUL = "MULTIPLE SOLUTIONS";
    const string NO = "NO SOLUTION";
   
    const int L = len + 1;
    const int S = f.size();
   
    int t[S][L];
    int p[S][L];
    fill( &t[0][0], &t[S-1][L], 0 );

    t[0][ f[0] ] = 1;
    t[0][ len - f[0] ] = 1;

    for(int i=0; i+1<S; ++i){
      for(int j=0; j<L; ++j){
        if( t[i][j] == 0 ) continue;
        int a = f[i + 1];
        int b = len - f[i + 1];
        if( j < a ){
          cout << i << " : " << j << " -> " << a << endl;
          t[i+1][ a ] += t[i][j];
          p[i+1][ a ] = j;
        }
        if( j < b && a != b ){
          cout << i << " : " << j << " -> " << b << endl;
          t[i+1][ b ] += t[i][j];
          p[i+1][ b ] = j;
        }
      }
    }   

    int cnt = 0;
    int idx;
    for(int i=0; i<L; ++i){
      cnt += t[S-1][i];
      if( t[S-1][i] ){
        cout << i << " : " << t[S-1][i] << endl;
        idx = i;
      }
    }      if( cnt == 0 )return NO;
    if( 1 < cnt )return MUL;

    vector<int> v;
    for(int i=S-1; 0<=i; --i){
      v.push_back( idx );
      idx = p[i][ idx ];
    }
    reverse( v.begin(), v.end() );
    ostringstream oss;
    for(int i=0; i<v.size(); ++i){
      if(i)oss << ' ';
      oss << v[i];
    }

    return oss.str();
}; 

1000