Edited by author 15.04.2008 23:22

program p1009;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var n,k:longint;
mas:array [0..25] of longint;
a:array [1..25] of longint;
min:longint;
procedure init;
var i:longint;
begin

 fillchar(mas,sizeof(mas),0);
 fillchar(a,sizeof(a),0);
 read(n);
 for i:=1 to n do
   read(a[i]);
end;
procedure print;
begin
 write(min);
 halt(0);
end;
function sc:longint;
var s1,s2,i:longint;
begin
 s1:=0;
 s2:=0;
 for i:=1 to n do
  if mas[i]=0 then inc(s1,a[i]) else inc(s2,a[i]);
 result:=abs(s1-s2);
end;
procedure generat;
var i,j:longint;
begin
  if mas[0]<>0 then print else
   begin
    j:=n;
    while mas[j]>0 do dec(j);
    mas[j]:=1;
    for i:=j+1 to n do
     mas[i]:=0;
    k:=sc;
    if k<min then min:=k;
    generat;
   end;
end;
begin
 init;
 min:=sc;
 generat;
 print;
end.

#include<iostream.h>
#include<math.h>

int i,j,a[35],n,max,min,max1,min1;

void main()
{

cin>>n;
 for(i=0;i<n;i++)
   cin>>a[i];

    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];

    }
    }


  max=a[n-1];
  min=a[n-2];
  i=n-3;

  while(i>=0)
  {
   if(max<min)
    max=max+a[i];
    else
    min=min+a[i];
    i--;
       }


  max1=a[1];
  min1=a[0];
  i=2;

  while(i<n)
  {
   if(max1<min1)
    max1=max1+a[i];
    else
    min1=min1+a[i];
    i++;
       }

   if(abs(max-min)>abs(max1-min1))
     cout<<abs(max1-min1);
      else
      cout<<abs(max-min);
 }

On my linux machine it works fine, when I submit the problem a got compilation error.

#include <iostream>
#include <vector>
using namespace std;
int data;
int last;
vector <int> base;
int pile[2];
vector <int>::iterator it;

int getMax(){
    it=base.end()-1;
    pile[0]+= *it;
    base.erase(it);
    return *it;
}

int getRest(int value){
    int all = 0;
    while(!base.empty()){
        it=base.end()-1;
        all += *it;
        if(value >= all){
            pile[1]+= *it;
            base.erase(it);
        }
        else{
            break;
        }

    }
    return 0;
}

int main(){
    last = 0;
    pile[0] = 0;
    cin >> data;
    while(cin >> data){
        base.push_back(data);
    }
    sort(base.begin(),base.end());
    while(!base.empty()){
        last = getMax();
        getRest(last);
    }
    if(pile[1] >= pile[0]){
    cout << pile[1] - pile[0];
    }
    else{
    cout << pile[0] - pile[1];
    }
    return 0;
}

Edited by author 22.03.2008 14:23

In the problem 1005 the result is "3" for the stones 5 5 8 13 27 14, but in my opinion the minimal weight is "2".
LEFT = 27, 5, 5 = 37
RIGHT = 13, 14, 8 = 35

LEFT - RIGHT = 2, not 3 shown in this problem.

Is there a bug, or I'm wrong ?

one in each line or all in single line.??

here is code:

    var
      a : array [1..20] of integer;
      y : array [1..2] of integer;
      j, n, min : integer;
   procedure asd(s, x : integer);
     var
       s1, i : integer;

     begin
     i := 1;
     while i <= 2 do
       begin
         if x+1<=n then
           begin
             s1 := abs(s + y[i]*a[x+1]);
             if x+1=n then  begin  if min>s1 then min := s1;  end
             else asd(s1, x+1);
           end
         else inc(i);
         inc(i);
       end;
     end;

begin
  read(n);
  for j := 1 to n do
  read(a[j]);
  min := 100000;
  y[1] := 1;   y[2] := -1;
  asd(a[1], 1);
  writeLn(min);
end.


Can anyone say me where my error is ???

thanks

#include<stdio.h>
#include<stdlib.h>
int split(int st[],int low,int high){                                         /*____________________*/
           int    k,i=low;
           int    temp;
           int    x=st[low];
                  for(k=low+1;k<=high;k++)
                            if (st[k]<=x){
                                        i=i+1;
                                        if(i!=k){
                                                 temp=st[i];
                                                 st[i]=st[k];                                                /*___sort____*/
                                                 st[k]=temp;
                                        }
                            }
                 {temp=st[low];st[low]=st[i];st[i]=temp;}
         return i;
}
void sort(int st[],int low,int high){
         int   k;
                 if(low<high){
                              k=split(st,low,high);
                              sort(st,low,k-1);
                              sort(st,k+1,high);
                 }
}                                                                                       /*___________________*/
int main()
{    int  i,j,stone;                   /*the number of stone*/
     int weight[20]={0};
     int sum,average;
     int min,max,value,temp=0;
                  while(scanf("%d",&stone)!=EOF){
                                   for(sum=0,i=1;i<=stone;i++){
                                                 scanf("%d",&weight[i]);
                                                 sum=sum+weight[i];
                                   }
                                   average=sum/2;
                                   sort(weight,1,stone);
                                   for(max=0,i=1;i<=stone;i++){
                                                 max=max+weight[i];
                                                 if(max>=average) break;
                                   }
                                   for(min=0,j=i+1;j<=stone;j++)
                                                min=min+weight[j];
                                   if(min>max){temp=max;max=min;min=temp;}
                                   for(value=sum,i=1;(max-min)>=0;i++){
                                                    if((max-min)<value) value=max-min;
                                                    max-=weight[i];
                                                    min+=weight[i];
                                   }
                                   printf("%d\n",value);
              }
     return 0;
}

Edited by author 02.11.2007 22:26

Edited by author 02.11.2007 22:26

I have solved it with Dp in 0.015.
Is there anyone fast(DP)?

# include <iostream.h>
int main()
{
    int W[21];
    int N,a,b;
    cin>>N;
    if (N>=1 && N<=20)
    {
        for (a=0;a<=N-1;a++)
            cin>> W[a];
        for (a=0;a<=N-2;a++)
        {
            for(b=a+1;b<=N-1;b++)
            {
                if (W[a]>W[b])
                {
                    W[a]=W[b]+W[a];
                    W[b]=W[a]-W[b];
                    W[a]=W[a]-W[b];
                }
            }
        }
        cout << W[1]-W[0];
    }
    return 0;
}

whywhywhywhy??????
i can't find any mistake!!!
(my English is very bad,sorry)

 var i,j,n,hoh,ha,hb:longint;
     a:array[0..21]of longint;
procedure hh(x,y:integer);
 begin
  if y=1 then inc(ha,a[x]) else inc(hb,a[x]);
  if x<=n then
   begin
    if x<n then hh(x+1,1) else if abs(ha-hb)<hoh then hoh:=abs(ha-hb);
    if x<n then hh(x+1,0) else if abs(ha-hb)<hoh then hoh:=abs(ha-hb);
   end;
 end;
begin
 readln(n);
 hoh:=maxlongint;
 for i:=1 to n do read(a[i]);
 ha:=0; hb:=0;
 hh(1,1);
 ha:=0; hb:=0;
 hh(1,0);
 writeln(hoh);
end.

#include <stdio.h>
#include <algorithm>

using namespace std ;

int main(int argc, char* argv[])
{
        int N ;
        long i ;
        double inta[100001];
        long sum1 , sum2 ;
        while(scanf("%d",&N)!=EOF)
        {
                for( i = 0 ;i < N ; i ++)
                        scanf("%lf",&inta[i] ) ;
                sort(inta , inta + N);
                sum1 = inta[N-1] ;
                sum2 = inta[N-2] ;
                for( i = N-3 ; i>=0 ;i--)
                {
                      if( sum1 >= sum2 )
                      {
                        sum2 += inta[i] ;
                      }
                      else
                        sum1 += inta[i] ;
                }
                printf("%ld\n",abs(sum1-sum2) );
        }
        return 0;
}
//---------------------------------------------------------------------------

hi , here is my code . why my program crashed.

/// code

 import java.io.* ;
 import java.util.* ;

  public class stonepile {

  public static void main(String args[]) throwsIOException {

BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));

    String str =null ;

   while((str=br.readLine())!=null) {
    //str=br.readLine() ;
   StringTokenizer st = new StringTokenizer(str," ") ;
   String s = st.nextToken() ;

      int []a = new int [50] ;
      int []dp =  new int [2000100] ;
      int  sum= 0 ;

       int n = Integer.parseInt(s) ;
         for ( int i = 0 ; i < n; i ++) {
           str = br.readLine() ;
             st = new StringTokenizer(str," ");
              s=st.nextToken() ;
              int m = Integer.parseInt(s) ;
               a[i] = m ;
                //sum +=m ;
          }

         dp[0] = 1 ;
          for ( int i = 0 ; i < n ; i++ ) {
              int c = a[i] ; sum+=c ;
            for ( int j = sum;  j -c >= 0 ; j--)
                 if ( dp[j-c]>0)
                      dp[ j ] = 1 ;

             }

          int y = -1 ,x = -1, j= -1 , r = 20000000 ;

            for ( int i = 1; i <sum+1 ; i++)
                 if ( dp[i]>0 && dp[sum-i]>0) {
                       x = Math.abs(i-(sum-i));
                       if ( r >x)
                           r=x  ;
             }

                    System.out.println(r) ;
           }
         }

      }

In this problem only there are only 20 stones(elements). So we can generate all possible variants of rearrange the stones into two piles. There will be 1,048,576 variants for 20 stones. Realization of such algorithm will work about 1 second(less than Time limit - 2 seconds). But I meet alike problem where can be about 60 elements. And in such case count of varians will decrease to 1,152,921,504,606,846,976. As you understand time limit in such way will be exeeded. I think than we have to use dinamic programming. Can anybody tell how to solve this problem with dinamic programming?

help me!!!
test:
1
1
Output = ?

My simple algorithm simply moves all subsets of the set and found them to a minimum. I moves every subset of the time I meet the right, but I get WA1 (why!)!
Please write 1 test!

Edited by author 14.08.2007 21:12

#include<stdio.h>
int main()
{
    long x[20],ans=0;
    int i=0,n=0;
    int j=0;
    long tmp=0,p[2];
    scanf("%ld",&n);
    for(i=0;i<n;i++) scanf("%ld",&x[i]);
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++) if(x[j-1]<x[j])
        {
            tmp=x[j];
            x[j]=x[j-1];
            x[j-1]=tmp;
        }
    }
    for(i=0;i<n;i++)
    {
        if(i<2) p[i]=x[i];
        else if(p[0]>p[1]) p[1]+=x[i];
        else p[0]+=x[i];
    }
    ans=p[1]-p[0];
    if(ans<0) ans=-ans;
    printf("%ld\n",ans);
}
My code worked all of my test cases.

Excuse for bad English.

There can be I of that do not understand, but if I have understood all, at you the first test wrong.

Input

5
5
8
13
27
14

Output

3

I have understood, that it is necessary to divide stones into 2 groups so that their weight was minimum, then

1st group

13
14
5
5

In the sum 37

2nd group

27
8

In the sum 35

As a result a difference not 3 and 2

Help please!

dert

here is my program; tell me what's wrong with it.plz.
program khosrow;
var
c,i,j,h,n,sum,sub:integer;
a,w:array[1..20]of integer;
begin
read(n);
sum:=0;
for i:=1 to n do
    begin
        readln(w[i]);
        sum:=sum+w[i];
    end;
c:=sum;
for i:=1 to n do
    a[i]:=0;
repeat
i:=0;
      repeat
            inc(i);
      until a[i]=0;
      a[i]:=1;
      for j:=1 to i-1 do
          a[j]:=0;
      sub:=0;
      for h:=1 to n do
          if a[h]=1 then sub:=sub+w[h];
      if c>abs(sum-(2*sub)) then
         c:=abs(sum-(2*sub));
until sub=sum;
writeln(c);
end.

f you have received WA1 that try to read not on strings.
For example:
read(n);
i:=1;
while not seekeof do
begin
  read(a[i]);
  inc(i);
end;
Probably you receive AC