Problem
La piccola Tina sta organizzando un tea party per le sue tre bambole. Ha n cioccolatini, per ognuno dei quali Tina conosce il suo parametro "cioccolato".
Tina vuole distribuire equamente le caramelle tra le bambole, vale a dire, è necessario distribuirle in modo che la differenza tra il contenuto totale di cioccolato più alto e quello più basso sia la più piccola possibile.
Inoltre, ogni caramella deve essere data a una delle tre bambole.
Inserimento:
La prima riga contiene un numero naturale n (1 <= n <= 12) - il numero di caramelle che ha Tina.
La seconda riga contiene n numeri naturali a
i separati da spazi - i parametri "cioccolato"; ogni caramella. 1 <= a
i <= 100.
Uscita:
Stampa un singolo numero: la differenza minima possibile tra il contenuto totale di cioccolato più grande e quello più piccolo.
Esempio:
| Input |
Uscita |
5
1 2 1 3 1
| 1 |
Spiegazione:
Puoi dare le prime due caramelle alla prima bambola, la terza e la quinta alla seconda bambola e la quarta alla terza bambola. Quindi il contenuto totale di cioccolato sarà pari rispettivamente a 3, 2 e 3. La differenza tra il più grande e il più piccolo è 3 - 2 = 1.