## 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;
}
```