POJ 1011

poj_1011.c

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ELEMENT 64
int num_of_sticks;
bool used[MAX_ELEMENT];
int sticks[MAX_ELEMENT];
int sum;

int cmp(const void *a, const void *b)
{
    return (*(int *)b) - (*(int *)a);
}

bool dfs(int cur, int left, int level, int len, int values_left)
{
    int i;
    if (left == 0) {
        if (level <= 1) {
            return true;
        }

        /* find the first unused one */
        for (i = 0; used[i]; i++) {
            /* pass */
        }

        used[i] = true;
        if (dfs(i+1, len - sticks[i], level-1, len, (level*len)-sticks[i])) {
            return true;
        }
        used[i] = false;
        return false;
    } else {
        if (cur >= num_of_sticks) {
            return false;
        }

        for (i = cur; i < num_of_sticks; i++) {
            if (used[i]) {
                continue;
            }

            if (left > values_left) {
                break;
            }

            if (sticks[i] == sticks[i-1] && !used[i-1]) {
                values_left -= sticks[i];
                continue;
            }

            if (sticks[i] <= left) {
                used[i] = true;
                values_left -= sticks[i];
                if (dfs(i+1, left-sticks[i], level, len, values_left)) {
                    return true;
                }
                used[i] = false;
            } else {
                values_left -= sticks[i];
            }
        }
    }

    return false;
}

int main(int argc, const char *argv[])
{

    while ((scanf("%d", &num_of_sticks)) && num_of_sticks != 0) {
        int i;
        sum = 0;
        for (i = 0; i < num_of_sticks; i++) {
            scanf("%d", &sticks[i]);
            sum += sticks[i];
        }

        qsort(sticks, num_of_sticks, sizeof(*sticks), cmp);

        int ret;
        for (ret = sticks[0]; ret <= sum; ret++) {
            if (sum % ret != 0) {
                continue;
            }

            bool found = true;
            memset(used, 0, sizeof(*used)*MAX_ELEMENT);

            found = dfs(0, 0, sum/ret, ret, sum);

            if (found) {
                printf("%d\n", ret);
                break;
            }
        }


    }

    return 0;
}