DMOPC '17 Contest 3 P3 - N-Kat

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Python 3.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.

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

• commented on Dec. 6, 2017, 3:02 p.m.

Hint for Python users getting TLE: try using Pypy instead.