LQDDIV - Chia nhóm
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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

Cần phân chia n người này vào 2 nhóm sao cho:

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

Dữ liệu

  • 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

Kết quả

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

Ví dụ

Input:

5
1 5 6 7 8

Output:

1 3

Chú thích: Độ chênh lệch ít nhất của 2 nhóm 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).

Giới hạn:  80% test với N ≤ 24


 
 
Back to Top