DHRECT - Trò chơi xếp hình chữ nhật
Giới hạn- Thời gian: 1.0s
- 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.
Xét trò chơi xếp hình chữ nhật với các que diêm như sau: Có n que diêm, que thứ i có độ dài di. Người chơi cần chọn ra 4 que diêm để có thể xếp thành một hình chữ nhật, giả sử 4 que diêm mà người chơi chọn có độ dài lần lượt là a, b, c, d (a ≤ b ≤ c ≤ d), khi đó có thể xếp được thành một hình chữ nhật nếu a = b và c = d. Người chơi xếp được hình chữ nhật có diện tích càng lớn sẽ càng được điểm cao.
Yêu cầu: Cho d1, d2,..,dn là độ dài của n que diêm. Hãy tìm cách chọn 4 que diêm để xếp được thành một hình chữ nhật có diện tích lớn nhất.
Dữ liệu: Vào từ thiết bị vào chuẩn: Dòng đầu tiên ghi số nguyên dương K là số lượng bộ dữ liệu. Tiếp đến là K nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:
- Dòng thứ nhất ghi một số nguyên dương n;
- Dòng tiếp theo chứa n số nguyên dương d1, d2,..,dn (di ≤ 10^9).
- Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra thiết bị ra chuẩn gồm K dòng, mỗi dòng ghi một số nguyên là diện tích của hình chữ nhật xếp được tương ứng với bộ dữ liệu trong file dữ liệu vào (ghi -1 nếu không tồn tại cách chọn nào xếp được hình chữ nhật).
Giới hạn:
- Subtask 1 (33%): Giả thiết là n ≤ 30.
- Subtask 2 (33%): Giả thiết là n ≤ 3000.
- Subtask 3 (33%): Giả thiết là n ≤ 300000.
Ví dụ:
Dữ liệu 2 5 5 3 1 5 1 4 1 2 3 4 Kết quả 5 -1
- Người up: beo_chay_so
- Nguồn bài: HSG Duyên hải & Ðồng bằng Bắc Bộ 2014