GCJ2018 Round2

README.md

• A small/large
• B small
• C small
• D small/large

a.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int tc; scanf("%d", &tc);
  for(int tci = 0; tci < tc; ++tci) {
    int nc; scanf("%d", &nc);
    int ballat[100];
    int maxdiff = 0;
    int bidx = 0;
    for(int i = 0; i < nc; ++i) {
      int bi;
      scanf("%d", &bi);
      for(int j = bidx; j < bidx+bi; ++j) {
        ballat[j] = i;
        maxdiff = max(maxdiff, abs(j-i));
      }
      bidx += bi;
    }
    if(ballat[0] != 0 || ballat[nc-1] != nc-1) {
      printf("Case #%d: IMPOSSIBLE\n", tci+1);
      continue;
    }
    printf("Case #%d: %d\n", tci+1, maxdiff+1);
    for(int i = 0; i <= maxdiff; ++i) {
      for(int j = 0; j < nc; ++j) {
        if(i+j<nc && ballat[i+j] < j) {
          printf("/");
        } else if(j-i>=0 && ballat[j-i] > j) {
          printf("\\");
        } else {
          printf(".");
        }
      }
      printf("\n");
    }
  }
  return 0;
}

b.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int tc; scanf("%d", &tc);
  for(int tci = 0; tci < tc; ++tci) {
    int nr, nb; scanf("%d%d", &nr, &nb);
    int score = 0;
    int histo[100] = {0};
    bool done = false;
    while(!done) {
      done = true;
      for(int badd = 0; badd <= nb; ++badd) {
        if(nr >= histo[badd]) {
          nr -= histo[badd]++;
          nb -= badd;
          ++score;
          done = false;
          break;
        }
        int movpos = -1, maxgain = -1;
        for(int i = 0; histo[i]; ++i) {
          int gain = histo[i] - histo[i+badd] - 1;
          if(gain > maxgain) {
            maxgain = gain;
            movpos = i;
          }
        }
        if(maxgain > 0) {
          --histo[movpos];
          ++histo[movpos+badd];
          nr += maxgain;
          nb -= badd;
          done = false;
          break;
        }
      }
    }
    printf("Case #%d: %d\n", tci+1, score-1);
  }
  return 0;
}

c.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main() {
  int tc; scanf("%d", &tc);
  for(int tci = 0; tci < tc; ++tci) {
    int n; scanf("%d", &n);

    int gstart = 4*n*n;
    int gend = 4*n*n+1;
    auto rowside = [=](int row, int color) -> int {
      return row * 2*n + color;
    };
    auto colside = [=](int col, int color) -> int {
      return 2*n*n + col * 2*n + color;
    };

    vector<vector<int>> graph(4*n*n+2);

    vector<int> dest;
    vector<int> flow;
    auto add_edge = [&](int a, int b) {
      graph[a].push_back(dest.size());
      dest.push_back(b);
      flow.push_back(1);
      graph[b].push_back(dest.size());
      dest.push_back(a);
      flow.push_back(0);
    };
    for(int i = 0; i < n; ++i) {
      for(int color = 0; color < 2*n; ++color) {
        add_edge(gstart, rowside(i, color));
      }
    }
    for(int i = 0; i < n; ++i) {
      for(int color = 0; color < 2*n; ++color) {
        add_edge(colside(i, color), gend);
      }
    }
    for(int row = 0; row < n; ++row) {
      for(int col = 0; col < n; ++col) {
        int color; scanf("%d", &color);
        color = color > 0 ? color - 1 : n + (-color - 1);
        add_edge(rowside(row, color), colside(col, color));
      }
    }
    vector<char> vis(graph.size());
    function<bool(int)> dig = [&](int v) -> bool {
      if(vis[v]) return false;
      vis[v] = true;
      if(v == gend) return true;
      for(int e : graph[v]) {
        if(flow[e] > 0 && dig(dest[e])) {
          --flow[e];
          ++flow[e^1];
          return true;
        }
      }
      return false;
    };
    int count = 0;
    while(dig(gstart)) {
      ++count;
      fill(vis.begin(), vis.end(), false);
    }
    printf("Case #%d: %d\n", tci+1, n * n - count);
  }
  return 0;
}

d.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main() {
  int tc; scanf("%d", &tc);
  for(int tci = 0; tci < tc; ++tci) {
    int nr, nc; scanf("%d%d", &nr, &nc);
    char table[30][30];
    for(int i = 0; i < nr; ++i) {
      scanf("%29s", table[i]);
    }
    bool possible[1<<4] = {false};
    for(int ii = 0; ii < 2*nr-1; ++ii) {
      for(int jj = 0; jj < 2*nc-1; ++jj) {
        int patno =
          (table[ii/2][jj/2]=='B') |
          ((table[ii/2][(jj+1)/2]=='B')<<1) |
          ((table[(ii+1)/2][jj/2]=='B')<<2) |
          ((table[(ii+1)/2][(jj+1)/2]=='B')<<3);
        possible[patno] = true;
      }
    }
    int maxcount = 0;
    for(int rsplit = 0; rsplit < nr; ++rsplit) {
      for(int csplit = 0; csplit < nc; ++csplit) {
        // int maxcount_at_split = 0;
        for(int patno = 0; patno < (1<<4); ++patno) {
          int rsym = (patno>>2) == (patno&3);
          int csym = ((patno>>1)&5) == (patno&5);
          if(rsym != !rsplit || csym != !csplit || !possible[patno]) continue;

          bool vis[20][20] = {false};
          int count;
          function<void(int, int)> search = [&](int i, int j) {
            if(vis[i][j]) return;
            vis[i][j] = true;
            char expected = "WB"[(patno >> ((i>=rsplit)*2 + (j>=csplit)))&1];
            if(table[i][j] == expected) {
              ++count;
              if(i>0) search(i-1, j);
              if(i<nr-1) search(i+1, j);
              if(j>0) search(i, j-1);
              if(j<nc-1) search(i, j+1);
            }
          };
          // int maxcount_at_pat = 0;
          for(int i = 0; i < nr; ++i) {
            for(int j = 0; j < nc; ++j) {
              count = 0;
              search(i, j);
              maxcount = max(maxcount, count);
              // maxcount_at_split = max(maxcount_at_split, count);
              // maxcount_at_pat = max(maxcount_at_pat, count);
            }
          }
          // fprintf(stderr, "(%d, %d, %d): %d\n", rsplit, csplit, patno, maxcount_at_pat);
        }
        // fprintf(stderr, "(%d, %d): %d\n", rsplit, csplit, maxcount_at_split);
      }
    }
    printf("Case #%d: %d\n", tci+1, maxcount);
  }
  return 0;
}