Problem
Cô bé Tina đang tổ chức tiệc trà cho ba con búp bê của mình. Cô ấy có n viên sô cô la, với mỗi viên đó Tina biết tham số "sô cô la" của cô ấy.
Tina muốn phân phối kẹo một cách công bằng giữa các con búp bê, cụ thể là cần phải phân phối chúng sao cho sự khác biệt giữa tổng hàm lượng sô cô la cao nhất và thấp nhất là nhỏ nhất có thể.
Ngoài ra, mỗi viên kẹo phải được trao cho một trong ba con búp bê.
Đầu vào:
Dòng đầu tiên chứa số tự nhiên n (1 <= n <= 12) - số kẹo Tina có.
Dòng thứ hai chứa n số tự nhiên a
i cách nhau bởi dấu cách - tham số "độ sô cô la"; mỗi viên kẹo. 1 <= a
i <= 100.
Đầu ra:
In một số duy nhất - chênh lệch nhỏ nhất có thể giữa tổng hàm lượng sô cô la lớn nhất và nhỏ nhất.
Ví dụ:
| Đầu vào |
Đầu ra |
5
1 2 1 3 1
| 1 |
Giải thích:
Bạn có thể đưa hai viên kẹo đầu tiên cho búp bê thứ nhất, viên kẹo thứ ba và thứ năm cho búp bê thứ hai và viên kẹo thứ tư cho búp bê thứ ba. Sau đó, tổng hàm lượng sô cô la sẽ lần lượt bằng 3, 2 và 3. Sự khác biệt giữa lớn nhất và nhỏ nhất là 3 - 2 = 1.