LQDDIV - Phân tập

Giới hạn
  • Thời gian: 0.109s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

Cho N người(2≤N≤32) ,mỗi người có một số a i (1 ≤ a i ≤ 10 9 ) được gọi là độ tin cậy

Cần phân chia n người này vào 2 tập sao cho:

  • Mỗi người thuộc đúng một tập
  • Chênh lệch tổng độ tin cậy của 2 phần là bé nhất

Input

Dòng đầu chứa số nguyên N

Dòng tiếp theo chứa N số : số thứ i là độ tin cậy của người thứ i

Output

Ghi ra hai số u và v với u là độ chênh lệch nhỏ nhất và v là số cách phân chia

Example

Input:
5 
1 5 6 7 8
Output:
1 3

Chú thích : Độ chênh lệch ít nhất của 2 phần là 1
                Có 3 cách phân chia .3 cách phân chia nhóm 1 là (3,5) ,(1,3,4) 
và (1,2,5)

  • Người up: kauke