//这道题一开始还不知道怎么做，后来一想，要是两组体重差最小，
//必然某一组极度接近总重的一半。显然又是一道背包。
#include <stdio.h>
int max(int a,int b)
{
        if(a>b) return a;
        else return b;
}
int main()
{
        int n,w[101]={0},allsum=0,i,r,f[10001];
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
                scanf("%d",&w[i]);
                allsum+=w[i];
        }
        int top=allsum/2;
        for(r=0;r<=top;r++)
                if(r<w[1]) f[r]=0;
                else f[r]=w[1];
        for(i=2;i<=n;i++)
                for(r=0;r<=top;r++)
                        if(r<w[i]) f[r]=f[r];
                        else f[r]=max(f[r],f[r-w[i]]+w[i]);
        printf("%d",allsum-2*f[top]);
        return 0;
}

//特别注意要强制类型转换。
//当然也可以不用。这是另一份参考：http://sfiction.blog.163.com/blog/static/199404010201110835749863/
#include <stdio.h>
int main()
{
        double sn=0;
        int k;
        int sum=0;
        scanf("%d",&k);
        while(sn<=k)
        {
                sum++;
                sn+=1/(double)sum;
        }
        printf("%d",sum);
        return 0;
}

//对对，我知道那个tj函数不用这样，但是这样代码就有重用的可能性了。
//水题，毕竟后来发现这是普及组的。
#include <stdio.h>
int sta[10]={0};
void tj(int k)
{
        if(k<10) sta[k]++;
        else
        {
                sta[k%10]++;
                tj(k/10);
        }
}
int main()
{
        int l,r;
        scanf("%d%d",&l,&r);
        int i;
        for(i=l;i<=r;i++) tj(i);
        printf("%d",sta[2]);
        return 0;
}

#include <stdio.h>
int max(int a,int b)
{
        if(a>b) return a;
        else return b;
}
int main()
{
        int ca[22]={0};
        int f[22][35001];
        int i,r;
        int b;
        int up;
        scanf("%d%d",&up,&b);
        for(i=1;i<=b;i++) scanf("%d",&ca[i]);
        for(r=0;r<=up;r++)
                if(r<ca[1]) f[1][r]=0;
                else f[1][r]=ca[1];
        for(i=2;i<=b;i++)
                for(r=0;r<=up;r++)
                {
                        if(r<ca[i]) f[i][r]=f[i-1][r];
                        else f[i][r]=max(f[i-1][r],f[i-1][r-ca[i]]+ca[i]);
                }
        printf("%d",f[b][up]);
        return 0;
}

//这道题的数学技巧比较强。
#include <stdio.h>
#include <math.h>
long int gcd(long int a,long int b)
{
        if(a%b!=0) return gcd(b,a%b);
        else return b;
}
int main()
{
        long int x,y;
        scanf("%ld%ld",&x,&y);
        long int i,num;
        num=0;
        for(i=x;i<=y;i++)
        {
                if(x*y%i==0&&x==gcd(i,x*y/i)) num++;
        }
        printf("%ld",num);
        return 0;
}

//先一次快排。以后挪一挪。
//贪心。
//又想起WJMZBMR曾经用这道题演示C++的STL。这样不就几乎不用做了吗？
#include<stdio.h>
#include<stdlib.h>
int comp(const void *p1,const void *p2)
    {
return *((int *)p1)-*((int *)p2);
}
int main()
{
int i,n,j,a[10001]={0},s=0,t;
scanf("%d",&n);
for(i=0;i<=n-1;i++) scanf("%d",&a[i]);
qsort(a,n,sizeof(int),comp);
for(i=0;i<=n-2;i++)
{
    a[i+1]=a[i]+a[i+1];
    s+=a[i+1];
    for(j=i+1;j<=n-2;j++) if(a[j]>a[j+1]) 
{
t=a[j];
        a[j]=a[j+1];
     a[j+1]=t;
}
}
printf("%d",s);
         return 0;
}

//模拟全过程就行了。
#include <stdio.h>
int main()
{
        int hp[8]={0,0,0,0,0,0,0,0};
        int i;
        for(i=1;i<=7;i++)
        {
                int a,b;
                scanf("%d%d",&a,&b);
                hp[i]=a+b;
        }
        for(i=1;i<=6;i++)
        {
                if(hp[i]>8) hp[i]-=8;
                else hp[i]=0;
     //           hp[i+1]+=hp[i];
        }
        if(hp[7]>8) hp[7]-=9;
        else hp[7]=0;
        int t=0,h=0;
        for(i=1;i<=7;i++)
        {
               if(hp[i]>h)
               {
                        t=i;
                        h=hp[i];
               }
        }
        printf("%d",t);
//        while(1);
        return 0;
}

//本来是可以用动规做的，但是也提供另一种方法
#include <stdio.h>
long int n,m;
int i,v[30],p[30];
long int maxget(int free,int now)
{
     if(now==-1) return 0;
     if(free-p[now]<0) return maxget(free,now-1);
     long int max1,max2;
     max1=maxget(free,now-1);
     max2=maxget(free-p[now],now-1)+v[now]*p[now];
     if(max1>max2)
     return max1;
     else
     return max2;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++) scanf("%d %d",&p[i],&v[i]);
    printf("%d",maxget(n,m-1));
    return 0;
}

//简单的01背包，可以参考饮食问题。（几乎一样，汗==）
#include <stdio.h>
int max(int a,int b)
{
        if(a>b) return a;
        else return b;
}
int main()
{
        int ca[31]={0};
        int f[31][20001];
        int i,r;
        int b;
        int up;
        scanf("%d%d",&up,&b);
        for(i=1;i<=b;i++) scanf("%d",&ca[i]);
        for(r=0;r<=up;r++)
                if(r<ca[1]) f[1][r]=0;
                else f[1][r]=ca[1];
        for(i=2;i<=b;i++)
                for(r=0;r<=up;r++)
                {
                        if(r<ca[i]) f[i][r]=f[i-1][r];
                        else f[i][r]=max(f[i-1][r],f[i-1][r-ca[i]]+ca[i]);
                }
        printf("%d",up-f[b][up]);
        return 0;
}

//规模不大，搜吧搜吧。
#include <stdio.h>
int n,m;
int map[101][101]={0};
int ans[101][101]={0};
int get(int x,int y)
{
        int sum,i;
        sum=0;
        for(i=1;i<=m;i++) sum+=map[x][i];
        for(i=1;i<=n;i++) sum+=map[i][y];
        return sum;
}
int main()
{
        int i,r;
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
                for(r=1;r<=m;r++)
                        scanf("%d",&map[i][r]);
        int max=0;
        for(i=1;i<=n;i++)
                for(r=1;r<=m;r++)
                        if(get(i,r)>max) max=get(i,r);
        printf("%d",max);
        return 0;
}