Hướng dẫn giải của Xếp hình

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, sussyboy, Luanhensam, asenen_kiet

Editorial for ptit031: Xếp hình

Hiểu bài toán

Cho 3 hình chữ nhật với kích thước (a1, b1), (a2, b2), (a3, b3). Nhiệm vụ là xác định xem có thể xếp 3 hình chữ nhật này thành một hình vuông duy nhất hay không. Nếu có, 출력 ra độ dài cạnh của hình vuông; ngược lại, in ra 0. Các hình chữ nhật có thể được xoay và sắp xếp theo bất kỳ thứ tự nào.

Các cách tiếp cận

Cách Brute Force (Tổ hợp tất cả các trường hợp)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct Rect { long long w, h; };
Rect rects[3];

bool check() {
    // Thử tất cả các hoán vị của 3 hình
    int p[] = {0, 1, 2};
    do {
        // Thử tất cả các cách xoay (2^3 = 8)
        for (int mask = 0; mask < 8; ++mask) {
            long long w1 = rects[p[0]].w, h1 = rects[p[0]].h;
            long long w2 = rects[p[1]].w, h2 = rects[p[1]].h;
            long long w3 = rects[p[2]].w, h3 = rects[p[2]].h;

            if (mask & 1) swap(w1, h1);
            if (mask & 2) swap(w2, h2);
            if (mask & 4) swap(w3, h3);

            // Case 1: Xếp dọc (cùng chiều rộng)
            if (w1 == w2 && w2 == w3 && w1 == h1 + h2 + h3) return true;

            // Case 2: Xếp 2 hình bên dưới 1 hình trên
            if (w1 == w2 && w1 + h3 == w3 && h1 + h2 == h3) return true;

            // Case 3: Xếp 2 hình bên cạnh 1 hình dưới
            if (h1 + h2 == h3 && w1 + w2 == w3 && w1 == w3) return true;
        }
    } while (next_permutation(p, p + 3));
    return false;
}

int main() {
    for (int i = 0; i < 3; ++i) cin >> rects[i].w >> rects[i].h;

    // Kiểm tra tổng diện tích có phải là số chính phương không
    long long totalArea = 0;
    for (int i = 0; i < 3; ++i) totalArea += rects[i].w * rects[i].h;

    long long side = sqrt(totalArea);
    if (side * side != totalArea) {
        cout << 0 << endl;
        return 0;
    }

    if (check()) cout << side << endl;
    else cout << 0 << endl;
    return 0;
}
  • Time Complexity: O(1) (vì số lượng hình cố định là 3, số lượng trường hợp là 3! * 2^3 = 48)
  • Space Complexity: O(1)

Phương pháp này thử tất cả các kết hợp có thể của 3 hình chữ nhật. Nó bao gồm:

  1. Tất cả các hoán vị của 3 hình (3! = 6 cách).
  2. Tất cả các cách xoay cho từng hình (2^3 = 8 cách).
  3. Với mỗi cấu hình, kiểm tra các cách xếp hình cơ bản:
    • Xếp 3 hình theo chiều dọc (cùng width).
    • Xếp 2 hình dưới đáy, 1 hình ở trên.
    • Xếp 1 hình ở dưới, 2 hình ở trên. Đây là cách tiếp cận trực quan nhất, đảm bảo không bỏ sót trường hợp nào.
Cách Optimization (Tối ưu hóa Logic)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;

struct Rect { long long w, h; };
Rect rects[3];

bool solve() {
    long long totalArea = 0;
    for (int i = 0; i < 3; ++i) totalArea += rects[i].w * rects[i].h;

    long long side = sqrt(totalArea);
    if (side * side != totalArea) return false;

    // Chỉ xét 1 hoán vị cố định, dùng hàm đệ quy/next_permutation
    // Hoặc dùng bitmask để tránh lặp
    vector<pair<long long, long long>> v;
    for(int i=0; i<3; ++i) v.push_back({rects[i].w, rects[i].h});
    sort(v.begin(), v.end());

    do {
        for (int mask = 0; mask < 8; ++mask) {
            long long w1 = v[0].first, h1 = v[0].second;
            long long w2 = v[1].first, h2 = v[1].second;
            long long w3 = v[2].first, h3 = v[2].second;
            if (mask & 1) swap(w1, h1);
            if (mask & 2) swap(w2, h2);
            if (mask & 4) swap(w3, h3);

            // Kiểm tra các cấu hình hình vuông
            // 1. Dọc: w = side, h = side
            if (w1 == side && w2 == side && w3 == side && h1 + h2 + h3 == side) return true;
            if (h1 == side && h2 == side && h3 == side && w1 + w2 + w3 == side) return true;

            // 2. 2 dưới 1 trên
            if (w1 == side && w2 == side && w1 + h3 == side && h1 + h2 == h3) return true;
            if (h1 == side && h2 == side && h1 + w3 == side && w1 + w2 == w3) return true;

            // 3. 1 dưới 2 trên
            if (w1 == side && w1 + h2 == side && w1 + h3 == side && h2 + h3 == side) return true;
            if (h1 == side && h1 + w2 == side && h1 + w3 == side && w2 + w3 == side) return true;
        }
    } while (next_permutation(v.begin(), v.end()));
    return false;
}

int main() {
    for (int i = 0; i < 3; ++i) cin >> rects[i].w >> rects[i].h;
    if (solve()) {
        long long side = sqrt(rects[0].w*rects[0].h + rects[1].w*rects[1].h + rects[2].w*rects[2].h);
        cout << side << endl;
    } else cout << 0 << endl;
    return 0;
}
  • Time Complexity: O(1)
  • Space Complexity: O(1)

Phương pháp này cũng dựa trên brute force nhưng được tối ưu hóa bằng cách:

  1. Kiểm tra xem tổng diện tích có phải là số chính phương trước. Nếu không, output 0 ngay lập tức.
  2. Dùng next_permutation và bitmask để duyệt các trường hợp thay vì viết lồng nhau.
  3. Kiểm tra logic dựa trên cạnh của hình vuông (side) đã tính được trước đó, giúp code ngắn gọn và dễ kiểm tra lỗi hơn.
Cách Sai lầm nghiêm trọng (Thiếu Logic)
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long a1, b1, a2, b2, a3, b3;
    cin >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;
    long long total = a1*b1 + a2*b2 + a3*b3;
    long long s = sqrt(total);
    if (s*s == total) cout << s;
    else cout << 0;
    return 0;
}
  • Time Complexity: O(1)
  • Space Complexity: O(1)

Đây là một giải pháp sai lầm phổ biến chỉ kiểm tra diện tích. Dù diện tích tổng bằng một số chính phương là điều kiện cần, nó không phải là điều kiện đủ. Ví dụ: 3 hình 1x6, 6x2, 3x6 có tổng diện tích 36, cạnh 6, nhưng không thể xếp thành hình vuông 6x6. Lưu ý: Code mẫu này lấy từ Solution 2 nhưng Logic của nó bị sai so với yêu cầu bài toán (hoặc bài toán gốc đã bị hiểu sai). Tuy nhiên, trong một số trường hợp bài toán có tên tương tự nhưng yêu cầu chỉ Output diện tích nếu có thể (vô nghĩa), giải pháp này là 'đúng' với câu hỏi 'Output side length if area is square'. Nhưng với bài toán 'Xếp hình', giải pháp này là sai.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(1) (vì số lượng hình cố định là 3, số lượng trường hợp là 3! * 2^3 = 48) O(1) Brute Force (Tổ hợp tất cả các trường hợp)
2 O(1) O(1) Optimization (Tối ưu hóa Logic)
3 O(1) O(1) Sai lầm nghiêm trọng (Thiếu Logic)

Bài học kinh nghiệm

  • Tổng diện tích của 3 hình phải bằng bình phương của một số nguyên (điều kiện cần).
  • Do số lượng hình nhỏ (3), có thể duyệt tất cả các trường hợp xoay và sắp xếp (48 trường hợp) một cách nhanh chóng.
  • Các cấu hình cơ bản để tạo hình vuông từ 3 hình chữ nhật bao gồm: 3 hình xếp dọc/cross, 2-1, 1-2.

Lỗi thường gặp

  • Chỉ kiểm tra tổng diện tích mà không kiểm tra việc ghép nối thực tế (Solution 2 là ví dụ điển hình của lỗi này nếu chỉ hiểu surface level).
  • Quên xoay các hình chữ nhật (chỉ xét w x h mà không xét h x w).
  • Lỗi tràn số (overflow) khi tính tổng diện tích nếu dùng int (nên dùng long long).

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.