Problem F (Northern European ACM Regional): Dividing coins
Description
Dutch legend has it that
copper-wire was invented in Holland when a husband and wife were fighting over a copper coin.
(after the tulip crash of the 1600's.)
The fighting was so fierce, they
stretched the coin to a great length and thus created the first conductor. Not as commonly
known is that the fighting started after the couple tried to divide a bag
with coins between the two of them. The contents of the bag appeared not to be
equally divisible. They couldn't stand the fact that a division
should favour one of them and they always wanted a fair share to the very last
cent. Nowadays fighting over a single cent is unlikely, but being
capable of making a division as fair as possible is something that will
remain important forever... .
Your task is to solve this problem.
Problem
Given a bag with a maximum of 100 coins, determine the fairest
division between two persons. This means that the difference between the amount
each person obtains should be minimized. The value of a coin varies from 1 cent
to 500 cents. It's not allowed to split a single coin.
Input
- a line with a non negative integer m (m <= 100) indicating
the number of coins in the bag
- a line with m numbers separated by one space, each number
indicates the value of a coin.
The above input may be repeated a number of times.
Output
There is one line of output for each pair of input lines.
Each output line is simply
the minimal positive difference between the amount the two persons obtain when
they divide the specified coins as equitably as possible.
Example
Sample input
3
2 3 5
4
1 2 4 6
Correct output for the sample input
0
1