2012年9月9日

UVa 307 - Sticks


I hate this problem...
#include <cstdio>
#include <algorithm>

int n, num[200], len, sides, found, ans;
bool check[200];

bool cmp(int a, int b) {
  return a > b;
}

void find(int sum, int now, int times) {
  if (times == (sides - 1)) {
    found = 1;
    return;
  }
  if (found) return;
  int i;
  for (i = now; i < n; i++) {
    if (check[i] || (sum + num[i]) > len) continue;
    if (i && num[i] == num[i - 1] && !check[i - 1]) continue;
    if (sum + num[i] == len) {
      check[i] = 1;
      find(0, 0, times + 1);
      check[i] = 0;
      return;
    } else if (sum + num[i] < len) {
      check[i] = 1;
      find(sum + num[i], i + 1, times);
      check[i] = 0;
      if (sum == 0) return;
      if (num[i] == sum - len) return;
    }
  }
}

int main() {
  while (scanf("%d", &n) && n) {
    int i, sum = 0;
    for (i = 0; i < n; i++) {
      scanf("%d", &num[i]);
      sum += num[i];
    }
    std::sort(num, num + n, cmp);
    found = 0;
    ans = 0;
    if (num[0] == num[n - 1]) {
      ans = num[0];
    } else {
      ans = sum;
      for (len = num[0]; len <= sum / 2; len++) {
        if (sum % len) continue;
        for (i = 0; i < n; i++) check[i] = 0;
        sides = sum / len;
        find(0, 0, 0);
        if (found) {
          ans = len;
          break;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言