George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input file contains blocks of 2 lines. The first line contains the number of sticks parts after cutting. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output file contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
Sample Output
6
5
先從大到小排序，在枚舉長度，從最長的棒子開始到總和的一半，負責就是總和，長度一定是總和的約數，
在深搜過程中，如果目前木棒和前一個木棒的長度是一樣的，但是前一個木棒沒有被選上，那麼這個木棒也一定不會被選上。
在深搜過程中，如果目前是在拼一根新木棒的第一截，但如果把可用的最長的一根木棒用上後不能拼成功的話，那麼就不用再試後面的木棒了，肯定是前面拼的過程出了問題。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;
int i, j, n, a[100], sum, c[100], tot, t, f;
void work(int x, int y, int z, int q)
{
int k = 1;
if (z == sum / x) { f = 1; return; }
for (int i = q; i < tot;i++)
if (c[i] && y + a[i] <= x)
{
c[i]--;
if (k&&y == 0) k = 0;
if (y + a[i] < x) work(x, y + a[i], z, i);
else {
work(x, 0, z + 1, 0);
if (f) return;
c[i]++;
break;
}
c[i]++;
if (!k) break;
}
}
int main() {
while (cin >> n, n)
{
for (i = 1, sum = 0, tot = 0; i <= n; i++)
{
cin >> t; sum += t;
for (j = 0; j<tot; j++) if (t == a[j]) break;
if (j == tot) {c[tot] = 0; a[tot++] = t;}
c[j]++;
}
for (i = 0; i<tot;i++)
for (j = i + 1; j<tot;j++)
if (a[i]<a[j]) { swap(a[i], a[j]); swap(c[i], c[j]); }
for (f = 0, i = n; i > 1; i--)
if (sum%i == 0 && sum / i >= a[0]) { work(sum / i, 0, 0, 0); if (f) break; }
end:cout << sum / i<< endl;
}
return 0;
}