SPOJ.com - Problem DHRECT

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/dhrect

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.

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

5 3 1 5 1

1 2 3 4

Kết quả

-1

Submit solution!

Đượ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

2021-05-27 18:01:02
Tham khảo: https://vnspoj.github.io/problems/DHRECT

2021-05-18 10:27:57
trâu 2 for AC, game dễ vl =))

Last edit: 2021-05-18 10:48:15

2019-03-22 19:58:54
@@ 91,67 point cho ai cần:
#include<iostream>
#include<map>
#define long long long
#define FOR(i, a, b) for(long i=a; i<=b; i++)
using namespace std;

map<long, long> d;
long max1, max2, T, n, a[300001];

long find_max(){
long MAX= -1, i;
FOR(j, 1, n)
if (d[ a[j] ]>=2 && MAX<a[j]){
MAX=a[j];
i=a[j];
}
d[i]-=2; //main
return MAX;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>T;
FOR(j, 1, T){
cin>> n;
FOR(i, 1, n) cin>> a[i];

FOR(i, 1, n) d[ a[i] ]=0;
FOR(i, 1, n) d[ a[i] ]++;

max1=find_max();
max2=find_max();
if (max1==-1 || max2==-1) cout<< -1<< endl;
else cout<< max1*max2<< endl;
}
}

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

Giải bài trực tuyến

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