Tìm cách xếp hình lớn nhất - LCOJ: Luyện Code Online Judge

MKRECT - Tìm cách xếp hình lớn nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Có ~N~ que diêm, que diêm thứ ~i~ có độ dài ~A_i~. Bạn cần chọn ra ~4~ que diêm khác nhau để tạo thành một hình chữ nhật, với các que diêm tạo

thành các cạnh. Tìm hình chữ nhật có diện tích lớn nhất mà có thể tạo được (có thể xem độ dày của các que diêm là không đáng kể).

Input

Dòng đầu tiên gồm số nguyên ~N~ ~(4 ≤ N ≤ 200000)~ - số que diêm;
Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^9)~ - độ dài của các que diêm.

Giới hạn:

Subtask #1 ~(30\%\text{ số điểm}): N ≤ 50~;
Subtask #2 ~(30\%\text{ số điểm}): N ≤ 2000~;
Subtask #3 ~(40\%\text{ số điểm}):~ Không có ràng buộc gì thêm.

Output

In ra diện tích lớn nhất trong số các hình chữ nhật có thể tạo được. Nếu không thể tạo ra hình chữ nhật nào thì in ra ~0~.

Sample

Input #1

7
9 5 5 2 3 1 3

Output #1

Input #2

5
4 4 4 4 1

Output #2

Input #3

4
9 8 7 6

Output #3

Hint

Trong ví dụ thứ nhất, ta chọn các que diêm thứ ~2, 3, 5, 7~. Khi đó ta tạo được hình chữ nhật có chiều dài ~5~, chiều rộng ~3~ và diện tích ~15~.
Trong ví dụ thứ hai, ta chọn các que diêm thứ ~1, 2, 3, 4~. Khi đó ta tạo được hình vuông có cạnh là ~4~ và diện tích ~16~. (Lưu ý rằng hình vuông là hình chữ nhật đặc biệt).

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

mducc đã bình luận lúc 2, Tháng 6, 2026, 14:05 ← chỉnh sửa →

Hint:

HCN cần 2 cặp que bằng nhau (cạnh dài và cạnh rộng).
Đếm tần suất mỗi độ dài, lấy các độ dài có cnt ≥ 2.
Sắp xếp các độ dài đó giảm dần.
Diện tích lớn nhất = tích của 2 giá trị lớn nhất (nếu có ≥ 2 loại).
Nếu 1 độ dài có cnt ≥ 4 → có thể thành hình vuông (cùng 1 cặp).

code tham khảo (c++):

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    map < long long, int> cnt;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        cnt[x]++;
    }
    vector < long long> v;
    for (auto &p : cnt) {
        if (p.second >= 2) v.push_back(p.first);
        if (p.second >= 4) v.push_back(p.first);
    }
    sort(v.rbegin(), v.rend());
    if (v.size() < 2) cout << "0\n";
    else cout << v[0] * v[1] << "\n";
    return 0;
}

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

int n;
cin >> n;
vector&lt;long long> a(n);
for (auto &x : a) cin >> x;

map&lt;long long, int> cnt;
for (long long x : a) cnt[x]++;

vector&lt;long long> pairs; // lưu độ dài tạo được cặp

for (auto &p : cnt) {
    if (p.second >= 2) pairs.push_back(p.first);
}

if (pairs.empty()) {
    cout << 0;
    return 0;
}

sort(pairs.rbegin(), pairs.rend());

long long ans = 0;

// Kiểm tra hình vuông (cùng một độ dài mà có >=4 que)
if (cnt[pairs[0]] >= 4)
    ans = pairs[0] * pairs[0];

// Kiểm tra hình chữ nhật với 2 cạnh khác nhau
if (pairs.size() >= 2)
    ans = max(ans, pairs[0] * pairs[1]);

cout << ans;
return 0;

}

0

MANHOOH đã bình luận lúc 16, Tháng 8, 2025, 9:04

đề có cho thừa cạnh ra không, không thì dùng map rồi chọn 2 key đầu tiên có tần suất > 2??