Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

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 ≤ 109).
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). Subtask 1 (20 điểm): Giả thiết là n ≤ 30. Subtask 2 (20 điểm): Giả thiết là n ≤ 3000. Subtask 3 (20 điểm): Giả thiết là n ≤ 300000.
Đ

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

 


Được gửi lên bởi:Lê Đôn Khuê
Ngày:2014-04-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:HSG Duyên hải & Đồng bằng Bắc Bộ 2014

hide comments
2019-01-07 09:42:26
.
2018-11-24 09:11:29
duckhiem243@gmail.com
ae cho e code vs ạ
2018-06-20 16:08:38
bạn nào cần :))))))
http://bit.ly/2FnpDYW

Last edit: 2019-01-12 01:59:22
2018-03-25 04:06:35
2 đấm AC
2018-01-05 01:58:42
ledacthuongvq
2017-04-20 11:19:05
đề bài lặp rồi.
2016-06-04 11:26:22
O(2NlogN) -> 83.33
O(NlogN) -> 100
2015-08-21 17:53:03 Thắng Ðam Mê
sửa Longint thành Int64 mới AC, làm sub tới lần thứ 2 :'(
2015-04-13 18:35:30 ??? Ares
trường hợp nào cũng có cần số lớn đâu :v dt tối đa là 10^18 thì QWord trong pascal hoặc long long C++ là đủ rồi :))
2015-02-22 16:34:21 Prismatic
Chú ý trường hợp a=b=c=d :)))
ko cần số lớn gì cả :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.