#include <iostream>
using namespace std;
int i,j,a[100001],n,maX,b,miN,minim[100001];
int sum = 0,sum1 = 0;
int main()
{
// input
cin >> n;
for (i = 0; i < n; i++)
cin>>a[i];

// sort from small to big ...
for (i = 0; i < n; i++)
{
  maX = a[i];
  for (j = i; j < n; j++)
  if (a[j] < maX)
  {
  a[i] = a[j];
  a[j] = maX;
  maX = a[i];
  }
}

for (int k = 0; k < n-1; k++)
{
sum += a[k];
if (sum > a[n-1])
{
miN = abs(sum - a[n-1]);
break;
goto end;
}
}

// doing any variants and adding result to minim[]
b = 0;
while (b < n)
{
maX = a[0];
for (i = 0; i < n; i++)
 for (j = i; j < n-1; j++)
 {
  a[i] = a[j+1]; break;
 }
a[n-1] = maX;
for (int k = 0; k < n/2; k++)
sum += a[k];
for (int k = n/2; k < n; k++)
sum1 += a[k];
minim[b] = abs(sum-sum1);
sum = 0; sum1 = 0;
b++;
}

// finding minimum
for (int k = 0; k < n; k++)
{
 miN = minim[k];
 for (int d = 0; d < n; d++)
 if (minim[d] < miN)
 {
 miN = minim[d];
 }
}
end:
cout<<miN;
return 0;
}



all my test works ... who know what's the first TEST?

Edited by author 24.10.2008 13:04

4
10
1
2
3

Thank you very much for test... I just remake some codes and get AC.

Can you show me better than my algorithm?

Edited by author 24.10.2008 18:11

Edited by author 24.10.2008 18:11

Its a simple Balance Partition Problem of Dynamic programming , Google it<