Hướng dẫn giải của Tạo hình vuông


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, Tuan_Kiettt, tieuc908, nguyenmaukhoi1909

Hiểu bài toán

Cho ba hình chữ nhật với kích thước (h1, w1), (h2, w2), (h3, w3) (với điều kiện h1 ≥ h2 ≥ h3 và wi ≤ hi). Nhiệm vụ là xác định xem có thể ghép ba hình chữ nhật này (có thể xoay) để tạo thành một hình vuông hoàn chỉnh mà không có khoảng trống ở giữa hay không. Ba hình chữ nhật phải được dùng hết và không được chồng lên nhau.

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

Cách Kiểm tra các cấu hình c cụ thể (Heuristic)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Rect {
    int w, h;
};

Rect a[3];
bool ok = false;

// Kiểm tra một cấu hình c cụ thể
bool check(Rect x, Rect y, Rect z) {
    long long area = 1LL * x.w * x.h + 1LL * y.w * y.h + 1LL * z.w * z.h;
    long long side = sqrt(area);
    if (side * side != area) return false;

    // Case 1: 3 hình xếp thành hàng/dọc
    if (x.h == y.h && y.h == z.h && x.h == side && x.w + y.w + z.w == side) return true;
    if (x.w == y.w && y.w == z.w && x.w == side && x.h + y.h + z.h == side) return true;

    // Case 2: 2 hình trên, 1 hình dưới
    if (x.w + y.w == side && x.h == y.h && x.h + z.h == side && z.w == side) return true;

    // Case 3: 2 hình dọc, 1 hình ngang
    if (x.h + y.h == side && x.w == y.w && x.w + z.w == side && z.h == side) return true;

    return false;
}

void backtrack(int i) {
    if (i == 3) {
        vector<int> p = {0, 1, 2};
        do {
            if (check(a[p[0]], a[p[1]], a[p[2]])) { ok = true; return; }
        } while (next_permutation(p.begin(), p.end()));
        return;
    }
    for (int j = 0; j < 2; ++j) {
        backtrack(i + 1);
        swap(a[i].w, a[i].h);
    }
}

int main() {
    for(int i=0; i<3; ++i) cin >> a[i].w >> a[i].h;
    backtrack(0);
    if (ok) cout << "YES";
    else cout << "NO";
    return 0;
}
  • Time Complexity: O(3! * 2^3) ~ O(48)
  • Space Complexity: O(1)

Phương pháp này dựa trên việc quan sát rằng có rất ít cách để ba hình chữ nhật tạo thành hình vuông. Ta thử tất cả các cách xoay (2^3 trường hợp) và tất cả các cách xếp thứ tự (3! trường hợp). Trong hàm check, ta kiểm tra các trường hợp đặc biệt như: 3 hình xếp thành 1 hàng, 2 hình trên 1 hình dưới, hoặc 2 hình dọc 1 hình ngang. Đây là cách tiếp cận nhanh và hiệu quả cho dữ liệu đầu vào nhỏ.

Cách Quy hoạch động bitmask
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

struct Rect { int w, h; };
Rect rects[8]; // Lưu tất cả các trạng thái xoay
int side;
int memo[1 << 3][205][205];

// dp[mask][r][c]: có thể điền vào hàng r, cột c với các hình trong mask hay không?
int dp(int mask, int r, int c) {
    if (mask == (1 << 3) - 1) return r == side && c == side;
    if (r == side && c == side) return 0;
    if (r > side || c > side) return 0;
    if (memo[mask][r][c] != -1) return memo[mask][r][c];

    // Nếu hàng hiện tại đã đầy, chuyển sang hàng mới
    if (c == side) return memo[mask][r][c] = dp(mask, r + 1, 0);

    // Thử đặt từng hình chữ nhật chưa dùng vào vị trí (r, c)
    for (int i = 0; i < 8; ++i) {
        if (!(mask & (1 << (i / 2)))) { // Kiểm tra xem hình gốc đã dùng chưa
            int w = rects[i].w;
            int h = rects[i].h;

            // Đặt hình vuông con tại (r, c)
            // Kiểm tra xem có thể điền vào các ô trong diện tích w x h không
            // (Ở đây ta đơn giản hóa: chỉ kiểm tra điều kiện biên)
            if (r + h <= side && c + w <= side) {
                // Tạo mask mới đánh dấu hình này đã dùng
                int new_mask = mask | (1 << (i / 2));
                // Thử điền tiếp từ vị trí tiếp theo
                if (dp(new_mask, r, c + w)) return memo[mask][r][c] = 1;
            }

            // Thử xoay nếu cần (đã có trong list 8 phần tử rồi, nên không cần xoay ở đây)
        }
    }
    return memo[mask][r][c] = 0;
}

int main() {
    int total_area = 0;
    for (int i = 0; i < 3; ++i) {
        int w, h; cin >> w >> h;
        rects[2 * i] = {w, h};
        rects[2 * i + 1] = {h, w};
        total_area += w * h;
    }
    side = sqrt(total_area);
    if (side * side != total_area) { cout << "NO"; return 0; }

    memset(memo, -1, sizeof(memo));
    if (dp(0, 0, 0)) cout << "YES";
    else cout << "NO";
    return 0;
}
  • Time Complexity: O(2^3 * side^2) ~ O(10^4)
  • Space Complexity: O(2^3 * side^2) ~ O(10^4)

Đây là phương pháp tổng quát hơn. Ta quy hoạch động trên bitmask mask đại diện cho các hình đã dùng, và tọa độ (r, c) là vị trí hiện tại để điền hình. Hàm dp(mask, r, c) trả về 1 nếu có thể hoàn thiện phần còn lại của hình vuông. Ta thử đặt từng hình chưa dùng vào vị trí (r, c) và điền tiếp. Tuy nhiên, cách này chỉ hoạt động tốt nếu các hình được xếp theo thứ tự hàng hoặc cột.

Cách Thử tất cả các trường hợp xếp hàng (Brute Force)
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

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

bool solve() {
    long long total_area = 0;
    for(int i=0; i<3; ++i) total_area += 1LL * rects[i].w * rects[i].h;
    long long side = sqrt(total_area);
    if (side * side != total_area) return false;

    // Sinh tất cả các hoán vị và xoay
    vector<int> p = {0, 1, 2};
    do {
        for (int m1 = 0; m1 < 2; ++m1) {
            for (int m2 = 0; m2 < 2; ++m2) {
                for (int m3 = 0; m3 < 2; ++m3) {
                    int r0_w = (m1 ? rects[p[0]].h : rects[p[0]].w);
                    int r0_h = (m1 ? rects[p[0]].w : rects[p[0]].h);
                    int r1_w = (m2 ? rects[p[1]].h : rects[p[1]].w);
                    int r1_h = (m2 ? rects[p[1]].w : rects[p[1]].h);
                    int r2_w = (m3 ? rects[p[2]].h : rects[p[2]].w);
                    int r2_h = (m3 ? rects[p[2]].w : rects[p[2]].h);

                    // Case 1: 3 hình xếp thành hàng ngang
                    if (r0_h == side && r1_h == side && r2_h == side && r0_w + r1_w + r2_w == side) return true;
                    // Case 2: 3 hình xếp thành hàng dọc
                    if (r0_w == side && r1_w == side && r2_w == side && r0_h + r1_h + r2_h == side) return true;

                    // Case 3: 2 hình trên, 1 hình dưới
                    if (r0_h + r1_h == side && r0_w == r1_w && r0_w == r2_w && r2_h == side) return true;
                    if (r0_h + r2_h == side && r0_w == r2_w && r0_w == r1_w && r1_h == side) return true;
                    if (r1_h + r2_h == side && r1_w == r2_w && r1_w == r0_w && r0_h == side) return true;

                    // Case 4: 2 hình dọc, 1 hình ngang
                    if (r0_w + r1_w == side && r0_h == r1_h && r0_h + r2_h == side && r2_w == side) return true;
                    if (r0_w + r2_w == side && r0_h == r2_h && r0_h + r1_h == side && r1_w == side) return true;
                    if (r1_w + r2_w == side && r1_h == r2_h && r1_h + r0_h == side && r0_w == side) return true;
                }
            }
        }
    } while (next_permutation(p.begin(), p.end()));
    return false;
}

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

Đây là cách tiếp cận trực quan nhất. Dựa trên phân tích, ba hình chữ nhật tạo thành hình vuông chỉ có thể xảy ra trong 2 trường hợp chính: (1) Cả 3 hình có cùng kích thước một cạnh bằng cạnh hình vuông và xếp lại (hình vuông đó là 3 mảnh dài), (2) Hai hình xếp chồng lên nhau (cùng chiều cao) và một hình bên dưới (hoặc tương tự). Vì số lượng hình ít, ta có thể thử tất cả các cách kết hợp xoay và xếp.

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

Cách tiếp cận Time Space Tên
1 O(3! * 2^3) ~ O(48) O(1) Kiểm tra các cấu hình c cụ thể (Heuristic)
2 O(2^3 * side^2) ~ O(10^4) O(2^3 * side^2) ~ O(10^4) Quy hoạch động bitmask
3 O(3! * 2^3) O(1) Thử tất cả các trường hợp xếp hàng (Brute Force)

Bài học kinh nghiệm

  • Tổng diện tích ba hình chữ nhật phải là một số chính phương (perfect square). Nếu không, đáp án chắc chắn là NO.
  • Vì số lượng hình ít (chỉ 3), số lượng cách ghép có giới hạn (6 cách sắp xếp thứ tự * 8 cách xoay = 48 trường hợp). Ta có thể kiểm tra tất cả các trường hợp này trong thời gian thường.
  • Các hình chữ nhật có thể được coi là các khối Lego. Việc ghép thành hình vuông yêu cầu các cạnh phải khớp nhau hoàn toàn.

Lỗi thường gặp

  • Quên kiểm tra xem tổng diện tích có phải là bình phương hay không trước khi thử các cấu hình.
  • Sai lệch trong việc tính toán các cạnh còn lại khi ghép (ví dụ: cạnh hình vuông trừ đi cạnh hình chữ nhật).
  • Bỏ qua các trường hợp xoay của các hình chữ nhật.

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.