hdu1059

#include <stdio.h> #include <string.h> #define MAXN 120005 int main() { int num[7]; int T = 0; while (scanf("%d %d %d %d %d %d", &num[1], &num[2], &num[3], &num[4], &num[5], &num[6]) != EOF) { T ++; if (!(num[1] || num[2] || num[3] || num[4] || num[5] || num[6])) break; int sum = 0; int i, j, k; for (i=1; i<=6; i++) sum += i * num[i]; if (sum % 2 != 0) { printf("Collection #%d:\nCan't be divided.\n\n", T); continue; } int total = sum / 2; bool flag[MAXN]; memset(flag, false, (total+1)*sizeof(flag[0])); flag[0] = true; for (i=1; i<=num[1]; i++) flag[i] = true; int much = num[1]; for (i=2; i<=6; i++) { if (num[i] == 0) continue; for (j=much; j>=0; j--) { if (flag[j]) { for (k=1; k<=num[i] && j + k * i <= total; k++) { if (flag[j + k * i]) break; flag[j + k * i] = true; } } } much += num[i] * i; } if (flag[total]) { printf("Collection #%d:\nCan be divided.\n\n", T); } else { printf("Collection #%d:\nCan't be divided.\n\n", T); } } return 0; }