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

Points: 7 (partial)

Time limit: 1.0s

Python 2.5s

Memory limit: 64M

Python 128M

Author:

Kirito

Problem type

Dr. Henri is a very busy person. He has $N$ $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$ $t_{1}$ seconds, and the tasks on day 2 take $t_2$ $t_{2}$ seconds, he wants to minimize the value of $|t_1 - t_2|$ $| t_{1} - t_{2} |$ .

The $i^\text{th}$ $i^{th}$ task takes him $A_i$ $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|$ $| t_{1} - t_{2} |$ if he partitions his tasks optimally?

Constraints

$0 \le A_i \le 700$ $0 \leq A_{i} \leq 700$

Subtask 1 [20%]

$1 \le N \le 20$ $1 \leq N \leq 20$

Subtask 2 [80%]

$1 \le N \le 700$ $1 \leq N \leq 700$

Input Specification

The first line of input will contain a single integer, $N$ $N$ .
The next and final line of input will contain $N$ $N$ space separated integers: $A_1, A_2, \dots, A_N$ $A_{1}, A_{2}, \dots, A_{N}$ .

Output Specification

Output the minimum value of $|t_1 - t_2|$ $| t_{1} - t_{2} |$ if Dr. Henri partitions the tasks optimally.

Sample Input

Copy

6
4 2 3 1 1 1

Sample Output

Copy

Explanation for Sample Output

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

Comments

15

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

note 1 day does not limited to 86400 seconds