I tried to solve problem with this algorithm:

1) Read numbers
2) Sort array descent
3) Put each element into smallest of two piles (start with largest element)
4) Answer will be abs(p1-p2)

And when I try - wrong answer in 5-th test appears.

What is wrong?

=============
Sourcecode :
=============
var S : array[0..20] of longint;
____N : integer;
____T : longint;
____I, J : integer;
____P1, P2 : longint;
begin
____read(N);
____for I := 1 to N do Read(S[I]);
____for I := 1 to N-1 do
________for J := I+1 to N do
____________if S[J] >= S[I] then begin
________________T := S[I];
________________S[I] := S[J];
________________S[J] := T;
____________end;
____P1 := 0;
____P2 := 0;
____for I := 1 to N do
________if P1<P2 then P1 := P1 + S[I]
_________________else P2 := P2 + S[I];
____write(abs(P2-P1));
end.

( '_' are whitespaces, I added them for most comfortable reading )

Well, so I did it at first time and got WA. Solution is DP. Here is a test which it fails: 5 weights: 6 6 5 5 2
your algo outputs 2 which is false, correct is 6, 6 and 5, 5, 2 -> 0 difference

Edited by author 13.08.2005 08:38