A KitKat is a candy bar that can be split into two equal sized pieces. One day while Christmas shopping, Roger stumbles upon the legendary -kat: a KitKat that can be split into
equally sized pieces, with the
piece having sweetness
. Roger wishes to split the pieces into two disjoint non-empty subsets to share with his two friends such that the total sweetness of the two subsets has the smallest possible non-negative difference. Note that the two subsets do not need to contain all
elements; Roger will eat any pieces his friends do not get. Help Roger split the
-kat!
Note that the judge will accept any valid solution.
Hint: It is recommended Python users use PyPy instead.
Constraints
Subtask 1 [20%]
Subtask 2 [80%]
Input Specification
The first line of input will contain a single integer, .
The next line of input will contain space-separated integers,
.
Output Specification
The output should consist of two lines.
The first line should contain , indicating that the first subset should contain piece
.
The second line should contain , indicating that the second subset should contain piece
.
Sample Input
4
8 2 3 1
Sample Output
2 4
3
Explanation for Sample Output
The first subset contains pieces and
, which have a total sweetness of
.
The second subset contains piece , which has a sweetness of
.
The difference between the total sweetness of both subsets is , which is the smallest difference possible.
Comments
Hint for Python users getting TLE: try using Pypy instead.