DGOLD - Chia vàng
Giới hạn- Thời gian: 0.4s
- 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.
Chuyện kể lại rằng, trong một lần thám hiểm hang động, Aladdin và thần đèn phát hiện một kho báu cổ xưa gồm N thỏi vàng ròng. Vẫn còn tiếc rẻ vì ngày trước ở trong hang thần không thó được món gì ngoài cây đèn cũ nát, Aladdin quyết tâm lần này sẽ mang hết vàng về. Ngặt nỗi kho báu này bị nguyền : nếu muốn đem K thỏi vàng ra khỏi hang thì K thỏi vàng này phải được chia thành 2 phần có khối lượng bằng nhau mà không được cắt, đập thỏi vàng nào ra cả. Nếu không làm đúng thì hang sẽ sập xuống chôn vùi tất cả, đến thần đèn cũng không cứu được.
Thần đèn dù tài phép vô biên nhưng tính toán lại rất kém, chỉ có thể hô biến ra một cái cân ký chứ không chọn được vàng. Aladdin cũng không hơn gì (lớn lên trên đường phố mà). Tuy nhiên Aladdin lại không chịu ra khỏi hang một khi chưa đem được lượng vàng nhiều nhất về. Thần đèn đang ngán ngẩm không biết khi nào Aladdin mới chọn vàng xong thì khỉ Abuxuất hiện. Nhanh như thoắt Abu đã chọn xong vàng và chia thành 2 túi có khối lượng đúng bằng nhau.Abu lại còn chọn được lượng vàng nhiều nhất nữa. Trong lúc Aladdin mừng hớn hở (vì bắt được vàng) thì thần đèn do chậm hiểu vẫn còn thắc mắc không biết một túi có bao nhiêu vàng. Hãy giúp thần đèn tìm con số này.
Input
Dòng đầu ghi số N – số thỏi vàng trong kho báu.
N dòng tiếp theo, dòng thứ i ghi số nguyên dương M i là khối lượng của thỏi vàng i (tính theo gam).
Giới hạn : 2 <= N <= 24
1 <= M i <= 40x10 6
Output
Ghi ra một số nguyên duy nhất là số gam vàng trong một túi của Abu.
Example
Input: 5 6000 30000 3000 11000 3000 Output: 6000
- Người up: yellowflash12
- Nguồn bài: by winterwolf94