Доставка

Задача: Оптимално разпределение на задачи

Имате $n$ задачи, които трябва да бъдат изпълнени. Всяка задача $i$ има определена трудност d_i. Трябва да разпределите тези задачи между два екипа, така че разликата в общата трудност на задачите, изпълнени от всеки екип, да бъде минимална.

Вход:

• Първият ред съдържа едно цяло число $n$ (1 \leq n \leq 1000) — броят на задачите.

• Вторият ред съдържа $n$ цели числа d_1, d_2, \ldots, d_n (1 \leq d_i \leq 1000) — трудностите на задачите.

Изход:

• Изведете едно цяло число — минималната възможна разлика в общата трудност на задачите между двата екипа.

Пример:

Вход:

5
1 2 3 4 5

Изход:

1

Обяснение:

Един възможен начин за разпределение на задачите е следният:

• Екип 1: задачи с трудности $1,4,5$ (обща трудност $10$)

• Екип 2: задачи с трудности $2,3$ (обща трудност $5$)

Разликата в общата трудност е |10 - 5| = 5. Въпреки това, по-добро разпределение би било:

• Екип 1: задачи с трудности $1,3,5$ (обща трудност $9$)

• Екип 2: задачи с трудности $2,4$ (обща трудност $6$)

Така разликата е |9 - 6| = 3. Най-доброто разпределение е:

• Екип 1: задачи с трудности $1,4$ (обща трудност $5$)

• Екип 2: задачи с трудности $2,3,5$ (обща трудност $6$)

Така разликата е |5 - 6| = 1, което е минималната възможна разлика.