DMOPC '18 Contest 4 P2 - Dr. Henri and Responsibility

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Python 5.0s
Memory limit: 64M
Python 128M

Problem type

Dr. Henri is a very busy person. He has N responsibilities to attend to over the next two days. Being a very organized person, he wants to split the tasks evenly between the two days. More specifically, if the tasks on day 1 take t_1 seconds, and the tasks on day 2 take t_2 seconds, he wants to minimize the value of |t_1 - t_2|.

The i^{\text{th}} task takes him A_i seconds, and must be completed within a single day. Dr. Henri, being very busy with these tasks, then asks you: what is the minimum value of |t_1 - t_2| if he partitions his tasks optimally?


0 \leq A_i \leq 700

Subtask 1 [20%]

1 \leq N \leq 20

Subtask 2 [80%]

1 \leq N \leq 700

Input Specification

The first line of input will contain an single integer, N. The next and final line of input will contain N space separated integers: A_1, A_2, A_3, \ldots, A_N

Output Specification

Output the minimum value of |t_1 - t_2| if Dr. Henri partitions the tasks optimally.

Sample Input

4 2 3 1 1 1

Sample Output


Explanation for Sample Input

If he partitions the task as \{2, 3, 1\} and \{4, 1, 1\}, they both sum to 6, and thus the difference is 0.


  • 1
    discoverMe  commented on Jan. 17, 2019, 2:31 p.m.

    note 1 day does not limited to 86400 seconds