2013年8月31日

UVa 10261 - Ferry Loading

#include <cstdio>
#include <cstring>

bool left[2001][10001];
int l[2001], prev[2001][10001];

void show(int now, int len) {
  if (!now) {
    return;
  }
  show(now - 1, prev[now][len]);
  puts(prev[now][len] == len ? "starboard" : "port");
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    n *= 100;
    memset(left, false, sizeof(left));
    left[0][0] = true;
    int now = 1, sum = 0, last = 0, len;
    while (scanf("%d", &l[now]) && l[now]) {
      sum += l[now];
      for (int i = 0; i <= n; i++) {
        if (sum - i <= n && left[now - 1][i]) {
          left[now][i] = true;
          prev[now][i] = i;
          last = now;
          len = i;
        } else if (i >= l[now] && left[now - 1][i - l[now]]) {
          left[now][i] = true;;
          prev[now][i] = i - l[now];
          last = now;
          len = i;
        }
      }
      now++;
    }
    printf("%d\n", last);
    show(last, len);
    if (T) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言