Problem B
Falling Apart
Languages
en
ja
After acquiring a new integer and showing it off to other
couples at a cocktail party, Alice and Bob headed home for a
good night of sleep. As their integer was quite large, they
were forced to carry it together. Then, on the Boole Boulevard,
right by the Bayes Bay, disaster struck. History does not tell
us which of our two protagonists stumbled first, but stumble
they did, and their integer shattered into
The couple’s marriage, already under financial stress due to
the expensive integer acquisition, did not survive this event,
and Bob and Alice resolved to separate. Thus the question was
raised on how to split the remnants of their integer. Bob and
Alice decided to play a game with the remaining
Bob and Alice, both very materialistic, seek to acquire the largest possible sum of integers possible. Compute the value of the integers each of them ends up with. Assume both players play optimally. Since A comes before B in the alphabet, Alice moves first.
Input
The input consists of two lines.
-
A single integer
, the number of pieces. -
The values of the pieces
, space-separated. It is given that .
Output
Output a single line containing two integers, the combined value of Alice’s pieces, and the combined value of Bob’s pieces.
Sample Input 1 | Sample Output 1 |
---|---|
3 3 1 2 |
4 2 |
Sample Input 2 | Sample Output 2 |
---|---|
4 1 2 2 1 |
3 3 |