# POJ 1258-Agri-Net

POJ 1258-Agri-Net
Agri-Net
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 40975 Accepted: 16713
Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
Source
USACO 102

The input includes several cases.

while(1)
{
scanf("%d",&n);
...
}


while(scanf("%d",&n)!=EOF)
{
...
}


#include<stdio.h>
int a;
int lowcost;
//int closet;
const static int MAX_DIS=100001; //最长距离
//prim算法求最小生成树
int prim(int n)
{
for(int i=0;i<n;i++)
{
lowcost[i]=a[i];
//closet[i]=0;//这个数组可以不要
}
int total_min_len=0;
int k,curr_min_len;
for(int t=0;t<n-1;t++)
{
k=0;
curr_min_len=MAX_DIS;
for(int i=0;i<n;i++)
{
if(lowcost[i]!=0&&lowcost[i]<curr_min_len)
{
curr_min_len=lowcost[i];
k=i;
}
}
total_min_len+=curr_min_len;//这题才是求和
//if(curr_min_len>total_min_len)//注意看题，求最小生成树中的最长路径
//     total_min_len=curr_min_len;
lowcost[k]=0;
for(int i=0;i<n;i++)
{
if(a[i][k]!=0&&a[i][k]<lowcost[i])
{
lowcost[i]=a[i][k];
//closet[i]=k;
}
}
}
return total_min_len;
}
int main()
{
int n;
//while(1)//The input includes several cases.并不代表case无穷
while(scanf("%d",&n)!=EOF)
{
//scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("%d\n",prim(n));
}
return 0;
}


# POJ 2485-Highways

POJ 2485-Highways
Highways
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 22907 Accepted: 10553
Description
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.
Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.
The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.
Input
The first line of input is an integer T, which tells how many test cases followed.
The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.
Output
For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.
Sample Input
1
3
0 990 692
990 0 179
692 179 0
Sample Output
692
Hint
Huge input,scanf is recommended.
Source
POJ Contest,Author:Mathematica@ZSU

which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

#include<stdio.h>
int a;
int lowcost;
int closet;
//prim算法求最小生成树
int prim(int n)
{
for(int i=0;i<n;i++)
{
lowcost[i]=a[i];
closet[i]=0;//这个数组可以不要
}
int total_min_len=0;
int k,curr_min_len;
for(int t=0;t<n-1;t++)
{
k=0;
curr_min_len=65537;
for(int i=0;i<n;i++)
{
if(lowcost[i]!=0&&lowcost[i]<curr_min_len)
{
curr_min_len=lowcost[i];
k=i;
}
}
//total_min_len+=curr_min_len;
if(curr_min_len>total_min_len)//注意看题，求最小生成树中的最长路径
total_min_len=curr_min_len;
lowcost[k]=0;
for(int i=0;i<n;i++)
{
if(a[i][k]!=0&&a[i][k]<lowcost[i])
{
lowcost[i]=a[i][k];
closet[i]=k;
}
}
}
return total_min_len;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("%d\n",prim(n));
}
return 0;
}


# hihoCoder 1051-补提交卡

hihoCoder 1051-补提交卡
#1051 : 补提交卡

3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90

76
59
100 #include<iostream>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
int n,m;
while(t--)
{
cin>>n>>m;
vector<int> a(n+1);
for(int i=0;i<n;i++)
cin>>a[i];
a[n]=101;//哨兵
if(m>=n)
cout<<100<<endl;
else
{
int max_days=0;//最长连续提交天数
int case_num=n-m+1;//总的枚举情况数
for(int i=0;i<case_num;i++)
{
int last_index=m+i-1;//该方案下最后一个下标
if(i==0)
{
if(a[last_index+1]-1>max_days)
max_days=a[last_index+1]-1;
}
else
{
if(a[last_index+1]-a[i-1]-1>max_days)
max_days=a[last_index+1]-a[i-1]-1;
}
}
cout<<max_days<<endl;
}
}
return 0;
}


# POJ 1019-Number Sequence

POJ 1019-Number Sequence
Number Sequence
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 34278 Accepted: 9835
Description
A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.
For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)
Output
There should be one output line per test case containing the digit located in the position i.
Sample Input
2
8
3
Sample Output
2
2
Source
Tehran 2002, First Iran Nationwide Internet Programming Contest

single_len=0; single_len=1; single_len=2; single_len=11. 因为single_len[i]为123...(i-1)i的长度，single_len[i-1]为123...(i-1)的长度。很显然，single_len[i]=single_len[i-1]+数字i的长度。这有点类似动态规划的状态转移方程。求数字i的长度可以用下面的函数求解：

//求数字i的位数
int get_digits_num(int i)
{
int rs=1;
while(i>=10)
{
rs++;
i/=10;
}
return rs;
}


1. 计算single_len和total_len。
2. 在total_len中二分查找位置i在以last_num为末尾数字的总的串中。
3. 计算出在以last_num为末尾数字的单个内部串中位置i所在的相对位置inner_index。
4. 在以last_num为末尾数字的单个内部串中二分查找出相对位置为inner_index的数字。

//（单组数字串）内部二分搜索
char bin_search_inner(int i)
{
int s=1,t=MAX_N,mid;
while(s<t)
{
mid=(s+t)/2;
if(single_len[mid]<i)
s=mid+1;
else if(single_len[mid]==i)
{
string s=int2string(mid);
return s[s.size()-1];
}
else
t=mid-1;
}
if(single_len[t]<i)
t++;
string rs=int2string(t);
return rs[rs.size()-(single_len[t]-i)-1];
}


#include<iostream>
#include<string>
#include<sstream>
#include<cstdlib>
using namespace std;
const static int MAX_N=31269;//数字串中最大的数
int single_len[MAX_N]={0};//single_len[i]表示1,2,3,...,i.这个数字串中总的数字位数
unsigned int total_len[MAX_N]={0};//total_len[i]表示1,12,123,...,123...i.这个数字串中总的数字位数
//将int转换为string
string int2string(int i)
{
stringstream ss;
string s;
ss<<i;
ss>>s;
return s;
}
//求数字i的位数
int get_digits_num(int i)
{
int rs=1;
while(i>=10)
{
rs++;
i/=10;
}
return rs;
}
//初始化单组数字串
void init_single_len()
{
for(int i=1;i<MAX_N;i++)
{
single_len[i]=single_len[i-1]+get_digits_num(i);
}
}
//初始化总体数字串
void init_total_len()
{
for(int i=1;i<MAX_N;i++)
{
total_len[i]=total_len[i-1]+single_len[i];
}
}
//外部（总体）二分搜索
int bin_search_outer(int i)
{
int s=1,t=MAX_N-1,mid;
while(s<t)
{
mid=(s+t)/2;
if(total_len[mid]<i)
s=mid+1;
else if(total_len[mid]==i)
return mid;
else
t=mid-1;
}
if(total_len[t]<i)
return t+1;
else
return t;
}
//（单组数字串）内部二分搜索
char bin_search_inner(int i)
{
int s=1,t=MAX_N,mid;
while(s<t)
{
mid=(s+t)/2;
if(single_len[mid]<i)
s=mid+1;
else if(single_len[mid]==i)
{
string s=int2string(mid);
return s[s.size()-1];
}
else
t=mid-1;
}
if(single_len[t]<i)
t++;
string rs=int2string(t);
return rs[rs.size()-(single_len[t]-i)-1];
}
int main()
{
int t,i;
cin>>t;
init_single_len();
init_total_len();
//cout<<total_len<<endl;
while(t--)
{
cin>>i;
int last_num=bin_search_outer(i);
int inner_index=i-total_len[last_num-1];
cout<<bin_search_inner(inner_index)<<endl;
}
return 0;
}


# hihoCoder 1043-完全背包

hihoCoder 1043-完全背包
#1043 : 完全背包

5 1000
144 990
487 436
210 673
567 58
1056 897

5940

#include <iostream>
#include<vector>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector<int> need_vi(n),value_vi(n);
for(int i=0;i<n;i++)
cin>>need_vi[i]>>value_vi[i];
vector<int> V(m+1,0);//V[j]表示有j张奖券，装前i个奖品获得的最大评分
for(int i=0;i<n;i++)//V[j]表示有j张奖券，装前i个奖品获得的最大评分，每个奖品可以装多个
{
for(int j=need_vi[i];j<=m;j++)//从前往后填表，因为这是完全背包
{
V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j];
}
}
cout<<V[m];
return 0;
}


# POJ 2586-Y2K Accounting Bug

POJ 2586-Y2K Accounting Bug
Y2K Accounting Bug
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10647 Accepted: 5328
Description
Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.
Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.
Input
Input is a sequence of lines, each containing two positive integers s and d.
Output
For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.
Sample Input
59 237
375 743
200000 849694
2500000 8000000
Sample Output
116
28
300612
Deficit
Source
Waterloo local 2000.01.29

ACM knows that each of these 8 postings reported a deficit

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int s,d;
while(cin>>s>>d)
{
int surplus_num;//盈余的月份数
vector<int> month(12,1);//初始的时候每个月都是surplus，1为surplus，0为deficit
for(int i=0;i<8;i++)//8个‘连续5个月’
{
surplus_num=0;
for(int j=0;j<5;j++)
surplus_num+=month[i+j];
int k=0;
while(surplus_num*s>=(5-surplus_num)*d)
{
month[i+4-k]=0;//亏损的月份尽量放到后面，因为可以和下一个周期重叠，这样总的surplus会大一些
surplus_num=0;
for(int j=0;j<5;j++)
surplus_num+=month[i+j];
k++;
}
}
surplus_num=0;
for(int i=0;i<12;i++)
surplus_num+=month[i];
int rs=surplus_num*s-(12-surplus_num)*d;//这一年总的盈亏
if(rs<0)
cout<<"Deficit"<<endl;
else
cout<<rs<<endl;
}
return 0;
}


1 2 3 4 5 6 7 8 9 10 11 12
s s s s d s s s s d s s //每5个月里只有1个月亏损
s s s d d s s s d d s s //每5个月里只有2个月亏损
s s d d d s s d d d s s //每5个月里只有3个月亏损
s d d d d s d d d d s d //每5个月里只有4个月亏损

#include<iostream>
using namespace std;
int main()
{
int a,b;
while(cin>>a>>b)
{
int ans = 0;
if(4*a-b<0)
{
ans = 10*a-2*b;
}
else if(3*a-2*b<0)
{
ans = 8*a-4*b;
}
else if(2*a-3*b<0)
{
ans = 6*a-6*b;
}
else if(a-4*b<0)
{
ans = 3*a-9*b;
}
else
{
ans = -1;
}
if(ans>0)
cout<<ans<<endl;
else
cout<<"Deficit"<<endl;
}
return 0;
}


# POJ 1012-Joseph

POJ 1012-Joseph
Joseph
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 48397 Accepted: 18267
Description
The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.
Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.
Input
The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.
Output
The output file will consist of separate lines containing m corresponding to k in the input file.
Sample Input
3
4
Sample Output
5
30
Source
Central Europe 1995

1. 因为坏人的编号大于k，所以m的取值肯定要大于k，要不然第一个杀的肯定是好人。
2. 对于某个m，最多只需要循环杀k个人，我们就能判断这个m是不是所求，杀人的过程中杀到某个人的编号小于等于k，则肯定杀到好人了，但此时还没有杀完所有坏人，所以这个m不是所求，跳出，m++；如果这k个人都成功杀完，则所有坏人都杀完，m是所求。

#include <stdio.h>
int main()
{
int people = {0}, k, Joseph = {0};//k最多是13，people所有人的编号，Joseph用于打表，不然超时
while(scanf("%d", &k) != EOF && k != 0)
{
if (Joseph[k] != 0)//如果是之前求过的
{
printf("%d\n", Joseph[k]);//则直接输出
continue;
}
int n = 2 * k;
int m = k+1;//m从k+1开始测试
people = 0;//people = 0表示编号从0开始
for (int i = 1; i <= k; i++)//最多连续杀k个人
{
//每次枚举完毕将剩下的人按从0到n - i编号，只要好人没有杀掉，则前面k - 1个编号是不变的
people[i] = (people[i - 1] + m - 1) % (n - i + 1);
if (people[i] < k)//第k个人的编号为k - 1,所以这里是<而不是<=    //杀到好人了
{
i = 0 ;//重新开始    //有点continue的意思
m++;  //测试下一个m
}
}
Joseph[k] = m;
printf("%d\n", m);
}
return 0;
}


#include<iostream>
#include<list>
#include<map>
using namespace std;
//测试m是否是所求
bool check_m(int k,int m)
{
list<int> li;
for(int i=1;i<=2*k;i++)
li.push_back(i);//首先初始化链表，人的编号从1开始
int pos=1,executed_num=0;//pos当前报数，executed_num被杀的人数
list<int>::iterator it=li.begin(),tmp;
while(executed_num<k)//最多杀k个人就可以判断m
{
if(pos==m)//如果报数到m了。
{
//cout<<*it<<endl;
if(*it<=k)//但是编号小于等于k，则杀到好人了。
return false;
tmp=it;
tmp++;
li.erase(it);//否则把这个坏人杀掉并去除这个节点
it=tmp;
pos=1;//重新从1开始报数
executed_num++;
}
else//如果还没报到m，则一直报下去，这个地方可能会消耗比较多的时间
{
pos++;
it++;
}
if(it==li.end())//如果到链表尾了，则循环到头
it=li.begin();
}
return true;
}
int main()
{
int k,m;
map<int,int> mii; //用于打表
while(cin>>k&&k)
{
if(mii.find(k)!=mii.end())//如果之前计算过这个k，则直接输出
{
cout<<mii[k]<<endl;
continue;
}
for(m=k+1;;m++)
{
if(check_m(k,m))
{
cout<<m<<endl;
mii[k]=m;
break;
}
}
}
return 0;
}


# hihoCoder 1040-矩形判断

hihoCoder 1040-矩形判断
#1040 : 矩形判断

3
0 0 0 1
1 0 1 1
0 1 1 1
1 0 0 0
0 1 2 3
1 0 3 2
3 2 2 3
1 0 0 1
0 1 1 0
1 0 2 0
2 0 1 1
1 1 0 1

YES
YES
NO

1. 有且只有4个互异的顶点 //点结构体
typedef struct P
{
int x,y;//两点坐标
bool operator<(const P& p)const//如果要加入到set中，需要重载<
{
//return this->x<p.x&&this->y<p.y;//注意这样会导致(0,0)<(0,1)且(0,1)<(0,0)的情况
return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));
}
bool operator==(const P&p)const//重载等于比较
{
return (this->x==p.x)&&(this->y==p.y);
}
};


return this->x<p.x&&this->y<p.y;


return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));


2. 矩形中某条边和另外3条边的关系是：和其中2条边垂直，和另外1条边平行
3. 且和它平行的那条边不能是重合的边

#include<iostream>
#include<set>
#include <vector>
using namespace std;
//点结构体
typedef struct P
{
int x,y;//两点坐标
bool operator<(const P& p)const//如果要加入到set中，需要重载<
{
//return this->x<p.x&&this->y<p.y;//注意这样会导致(0,0)<(0,1)且(0,1)<(0,0)的情况
return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));
}
bool operator==(const P&p)const//重载等于比较
{
return (this->x==p.x)&&(this->y==p.y);
}
};
//线结构体
typedef struct L
{
P p1,p2;//一条线由两点组成
};
//判断两条线的关系，1：垂直 0：平行 -1：其他
int check_two_line(L l1,L l2)
{
int x1=l1.p1.x,y1=l1.p1.y,x2=l1.p2.x,y2=l1.p2.y;
int a1=l2.p1.x,b1=l2.p1.y,a2=l2.p2.x,b2=l2.p2.y;
if((y2-y1)*(b2-b1)==-(x2-x1)*(a2-a1))//斜率公式的变形
return 1;
else if((y2-y1)*(a2-a1)==(b2-b1)*(x2-x1))
return 0;
else
return -1;
}
//判断是否是同一条直线
bool is_same_line(L l1,L l2)
{
if(((l1.p1==l2.p1)&&(l1.p2==l2.p2))||((l1.p1==l2.p2)&&(l1.p2==l2.p1)))//如果线的两个端点都相同，则是同一条直线
return true;
else
return false;
}
//判断能否组成一个矩形
bool is_rect(vector<L> lines)
{
int vertical_num,parallel_num;
for(int i=0;i<4;i++)//每条线都和剩余3条线判断关系
{
vertical_num=0;
parallel_num=0;
for(int j=0;j<4;j++)
{
if(j==i)//不和自己判断
continue;
int rs=check_two_line(lines[i],lines[j]);
if(rs==-1)
return false;
else if(rs==1)
vertical_num++;
else
{
if(is_same_line(lines[i],lines[j]))//如果是平行线还要判断是否是相同的线
return false;
parallel_num++;
}
}
if(!(vertical_num==2&&parallel_num==1))//只有当该线和其他2条线垂直，1条线平行时，才能组成矩形
return false;
}
return true;
}
int main()
{
int T;
cin>>T;
while(T--)
{
set<P> points;
vector<L> lines;
for(int i=0;i<4;i++)
{
P p1,p2;
cin>>p1.x>>p1.y>>p2.x>>p2.y;
points.insert(p1);
points.insert(p2);
L l;
l.p1=p1;
l.p2=p2;
lines.push_back(l);
}
if(points.size()!=4)//能组成矩形的必要条件是有且只有4个点，所以用set来判断更方便
cout<<"NO"<<endl;
else
{
if(is_rect(lines))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}


# hihoCoder 1038-01背包

hihoCoder 1038-01背包
#1038 : 01背包

5 1000
144 990
487 436
210 673
567 58
1056 897

2099

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector<int> need_vi(n);//所需奖券
vector<int> value_vi(n);//评分值
for(int i=0;i<n;i++)
cin>>need_vi[i]>>value_vi[i];
vector<int> V(m+1,0);//V[j]表示有j张奖券，装前i个奖品获得的最大评分
for(int i=0;i<n;i++)//V[j]表示有j张奖券，装前i个奖品获得的最大评分
{
for(int j=m;j>=need_vi[i];j--)//从后往前填表，能减少空间
{
V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j];//要这件奖品和不要的对比
}
}
cout<<V[m];
return 0;
}


# POJ 1011-Sticks

POJ 1011-Sticks
Sticks
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 121990 Accepted: 28247
Description
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 contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should 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
Source
Central Europe 1995

#include <iostream>
#include<algorithm>
using namespace std;
int total_sticks,n,original_len;//分别表示没截断之前有几根棍子，总的截断的数量，没截断之前每根棍子的长度
int sticks;//截断之后每部分的长度
int mark;//指示每一段是否搜索过了
void init_mark()
{
for(int i=0;i<65;i++)
mark[i]=0;
}
bool cmp(int a,int b)
{
return a>b;
}
//深度搜索，参数分别表示已经拼接好了几根棍子，当前正在拼接的棍子已经拼了多长了，当前测试的下标
bool dfs(int done_sticks,int done_parts,int pos)
{
if(done_sticks==total_sticks)//如果所有棍子都拼好了，成功
return true;
for(int i=pos+1;i<n;i++)//从pos+1开始测试
{
if(mark[i]==1)//如果这根小棍子已经拼过了，则开始下一个
continue;
if(done_parts+sticks[i]==original_len)//刚好拼成了一个原始的棍子
{
mark[i]=1;//标记
if(dfs(done_sticks+1,0,-1))//继续深度搜索，注意pos=-1，因为之前搜索的时候有些前面的小棍子可能没用上
return true;
mark[i]=0;//如果搜索失败，回溯
return false;
}
else if(done_parts+sticks[i]<original_len)
{
mark[i]=1;
if(dfs(done_sticks,done_parts+sticks[i],i))//继续深度搜索，这时pos=i，因为继续往下搜的过程中，只能越取越小，因为这个时候还没有拼成一个完整的棍子，且之前已经搜过大的了
return true;
mark[i]=0;//如果搜索失败，回溯
if(done_parts==0)//如果这根小棍子是某次拼接时的第一个棍子，则失败
return false;
while(sticks[i]==sticks[i+1])//否则找下一个小棍子时，跳过数值相同的小棍子，因为肯定失败
i++;
}
}
return false;
}
int main()
{
while(cin>>n&&n)
{
int sum=0;
for(int i=0;i<n;i++)
{
cin>>sticks[i];
sum+=sticks[i];//求和
}
sort(sticks,sticks+n,cmp);//按降序排序
for(original_len=sticks;original_len<=sum;original_len++)
{
if(sum%original_len==0)//总和肯定能被原始棍子的长度整除
{
total_sticks=sum/original_len;
init_mark();//每次都要初始化
if(dfs(0,0,-1))//dfs初始值
{
cout<<original_len<<endl;
break;
}
}
}
}
return 0;
}