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

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Python 2.5s
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 \le A_i \le 700

Subtask 1 [20%]

1 \le N \le 20

Subtask 2 [80%]

1 \le N \le 700

Input Specification

The first line of input will contain a single integer, N.
The next and final line of input will contain N space separated integers: A_1, A_2, \dots, 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 Output

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


  • 15
    discoverMe  commented on Jan. 17, 2019, 7:31 p.m.

    note 1 day does not limited to 86400 seconds