DMOPC '17 Contest 3 P3 - N-Kat

View as PDF

Submit solution

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

Problem type

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 N-kat: a KitKat that can be split into N equally sized pieces, with the i^\text{th} piece having sweetness s_i. 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 N elements; Roger will eat any pieces his friends do not get. Help Roger split the N-kat!

Note that the judge will accept any valid solution.

Hint: It is recommended Python users use PyPy instead.


1 \le s_i \le 10^6

Subtask 1 [20%]

2 \le N \le 10

Subtask 2 [80%]

2 \le N \le 20

Input Specification

The first line of input will contain a single integer, N.
The next line of input will contain N space-separated integers, s_1, s_2, \dots, s_N.

Output Specification

The output should consist of two lines.
The first line should contain a_1\ a_2\ \dots, indicating that the first subset should contain piece a_1, a_2, \dots.
The second line should contain b_1\ b_2\ \dots, indicating that the second subset should contain piece b_1, b_2, \dots.

Sample Input

8 2 3 1

Sample Output

2 4

Explanation for Sample Output

The first subset contains pieces 2 and 4, which have a total sweetness of 3.
The second subset contains piece 3, which has a sweetness of 3.
The difference between the total sweetness of both subsets is 0, which is the smallest difference possible.


  • 0
    Kirito  commented on Dec. 6, 2017, 8:02 p.m.

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