Trò chơi xếp hình chữ nhật

View as PDF

Submit solution


Points: 0.62 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HSG Duyên hải & Ðồng bằng Bắc Bộ 2014
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 ~d_i~. 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 \leq b \leq c \leq 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 ~d_1~, ~d_2~, ..., ~d_n~ 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.

Input

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 ~d_1~, ~d_2~, ..., ~d_n~ ~(d_i \leq 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.

Output

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 \leq 30~.
  • Subtask ~2~ ~(33\%)~: Giả thiết là ~n \leq 3000~.
  • Subtask ~3~ ~(33\%)~: Giả thiết là ~n \leq 300000~.

Sample Input

2
5
5 3 1 5 1
4
1 2 3 4

Sample Output

5
-1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.