/*
题意：若干小木棍，是由多条相同长度的长木棍分割而成，问最小的原来长木棍的长度；
DFS剪枝：剪枝搜索的好题！TLE好几次，终于剪枝完全！
剪枝主要在4和5：4 相同长度的木棍不再搜索；5 若新的搜索连第一条都没组合出来，直接break；
详细解释：http://blog.csdn.net/lyy289065406/article/details/6647960
http://www.cnblogs.com/devil-91/archive/2012/08/03/2621787.html
这题虐我千百遍，我待她如。。 656K 0MS 博客随笔第100篇，纪念一下:)
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std; const int MAXN = ;
const int INF = 0x3f3f3f3f;
int a[MAXN];
bool vis[MAXN];
int sum;
int n, cnt; bool cmp(int x, int y)
{
return x > y;
} bool DFS(int len, int ans, int num, int s)
{
if (num == cnt) return true; int pre = -;
for (int i=s; i<=n; ++i)
{
if (vis[i] || a[i] == pre) continue; //Cut 4 vis[i] = true;
if (ans + a[i] < len)
{
if (DFS (len, ans + a[i], num, i) == true) return true;
else pre = a[i];
}
else if (ans + a[i] == len)
{
if (DFS (len, , num+, ) == true) return true;
else pre = a[i];
}
vis[i] = false; if (ans == ) break; //Cut 5
} return false;
} int main(void) //POJ 1011 Sticks
{
//freopen ("POJ_1011.in", "r", stdin); while (scanf ("%d", &n) == && n)
{
sum = ; memset (vis, , sizeof (vis));
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]); sum += a[i];
}
sort (a+, a++n, cmp); //Cut 1 bool flag = false;
for (int i=a[]; i<=sum-i; ++i) //Cut 2
{
if (sum % i == ) //Cut 3
{
cnt = sum / i;
if (DFS (i, , , ) == true)
{
flag = true;
printf ("%d\n", i); break;
}
}
}
if (!flag) printf ("%d\n", sum);
} return ;
} /*
6
5
*/