Problem
La petite Tina organise un goûter pour ses trois poupées. Elle a n chocolats, pour chacun desquels Tina connaît son paramètre "chocolat".
Tina souhaite répartir équitablement les bonbons entre les poupées, à savoir qu'il faut les répartir de manière à ce que la différence entre la teneur totale en chocolat la plus élevée et la plus faible soit la plus faible possible.
De plus, chaque bonbon doit être donné à l'une des trois poupées.
Saisie :
La première ligne contient un nombre naturel n (1 <= n <= 12) - le nombre de bonbons que Tina a.
La deuxième ligne contient n nombres naturels a
i séparés par des espaces - les paramètres "chocolatité" ; chaque bonbon. 1 <= a
i <= 100.
Sortie :
Imprimez un seul chiffre - la différence minimale possible entre la teneur totale en chocolat la plus élevée et la plus petite.
Exemple :
| Entrée |
Sortie |
5
1 2 1 3 1
| 1 |
Explication :
Vous pouvez donner les deux premiers bonbons à la première poupée, les troisième et cinquième à la deuxième poupée et le quatrième à la troisième poupée. Ensuite, la teneur totale en chocolat sera égale à 3, 2 et 3, respectivement. La différence entre le plus grand et le plus petit est 3 - 2 = 1.