Задача
Крошка Тина устраивает чаепитие для трех своих кукол. У нее есть n конфет, для каждой из которых Тина знает ее параметр "шоколадности".
Тина хочет честно разделить конфеты между куклами, а именно, необходимо распределить их так, чтобы разница между наибольшей суммарной шоколадностью и наименьшей была минимально возможной.
При этом каждую конфету нужно отдать одной из трех кукол.
Входные данные:
Первая строка содержит натуральное число n (1 <= n <= 12) - количество конфет у Тины.
Вторая строка содержит n натуральных чисел a
i, разделенных пробелами - параметры "шоколадности" каждой конфеты. 1 <= a
i <= 100.
Выходные данные:
Выведите одно число - минимально возможную разницу между наибольшей суммарной шоколадностью и наименьшей.
Пример:
| Входные данные |
Выходные данные |
5
1 2 1 3 1 |
1 |
Пояснение:
Можно отдать первые две конфеты первой кукле, третью и пятую второй кукле и четвертую третьей кукле. Тогда суммарные шоколадности будут равны 3, 2 и 3 соответственно. Разница между наибольшей и наименьшей равна 3 - 2 = 1.