Problem
A pequena Tina está dando um chá para suas três bonecas. Ela tem n chocolates, para cada um dos quais Tina conhece seu parâmetro "chocolate".
A Tina quer distribuir de forma justa os bombons entre as bonecas, ou seja, é necessário distribuí-los de forma que a diferença entre o maior teor total de chocolate e o menor seja a menor possível.
Além disso, cada doce deve ser entregue a uma das três bonecas.
Entrada:
A primeira linha contém um número natural n (1 <= n <= 12) - o número de doces que Tina tem.
A segunda linha contém n números naturais a
i separados por espaços - os parâmetros "chocolateness"; cada doce. 1 <= a
i <= 100.
Saída:
Imprima um único número - a diferença mínima possível entre o maior conteúdo total de chocolate e o menor.
Exemplo:
| Entrada |
Saída |
5
1 2 1 3 1
| 1 |
Explicação:
Você pode dar os dois primeiros doces para a primeira boneca, o terceiro e o quinto para a segunda boneca e o quarto para a terceira boneca. Então o teor total de chocolate será igual a 3, 2 e 3, respectivamente. A diferença entre o maior e o menor é 3 - 2 = 1.