SRM452Div2

250

class EggCartons {
public:
  int minCartons(int n) {
    const int size = n + 1 + 8;
    const int inf = 1 << 24;
    int t[size];
    fill( t, t + size, inf );
    t[0] = 0;
    for(int i=0; i<n; ++i){
      t[i+6] = min( t[i+6], t[i] + 1 );
      t[i+8] = min( t[i+8], t[i] + 1 );
    }
    return t[n] == inf ? -1 : t[n];
  }
};

500

class NotTwo {
public:
  int maxStones(int width, int height) {

    const int H    = 1000 + 1, W =    1000 + 1;
    static char g[H][W];
    fill( &g[0][0], &g[H-1][W], '.' );

    char c = 'A';

    for(int i=0; i<height && i<2; ++i){
      for(int j=0; j<width && j<2; ++j){
        for(int k=i, line=0; k<height; k+=2){
          int cnt = 0;
          for(int l=j; l<width; l+=2){
            if( cnt++ % 2 == line )g[k][l] = c;
          }
          line ^= 1;
        }
        ++c;
      }
    }

    return H * W - count( &g[0][0], &g[H-1][W], '.' );
  }
};

1000
できてみると簡単だけど、相当悩んだ。

const int N = 50;

bool vis[N];

void rec(int node, vector<string> f)
{
  vis[node] = true;
  for(int i=0; i<f.size(); ++i){
    if( !vis[i] && f[node][i] == 'Y' )rec(i, f);
  }
  return ;
}

class HamiltonPath {
public:
  int countPaths(vector <string> f) {

    const int size = f.size();

    fill( vis, vis + size, false );
    int    parts =    0;
    int    cnt = 0;
    for(int i=0; i<size; ++i){
      int y = count( f[i].begin(), f[i].end(), 'Y' );
      if( 2 < y )return    0;
      if( !vis[i] && y <= 1 ){
        rec(i, f);
        ++parts;
    if(y)++cnt;
      }
    }

    if( count( vis, vis + size, false ) )return    0;

    const lli mod = 1000000007;
    lli ret = (1LL << cnt) % mod;
    for(lli i=1; i<=(lli)parts; ++i){
      ret = ret * i % mod;
    }

    return (int)ret;
  }
};