Editorial for msquare: Cắt hình vuông

Hiểu bài toán

Bài toán yêu cầu vẽ một hình vuông cạnh a (sử dụng ký tự '' và dấu cách) nhưng bị cắt bỏ một hình vuông nhỏ cạnh b ở góc dưới bên phải. Hình vuông lớn có tọa độ từ (0,0) đến (a-1, a-1). Hình vuông bị cắt nằm ở góc dưới bên phải, bao gồm các ô có hàng từ a-b đến a-1 và cột từ a-b đến a-1. Các ô này sẽ là khoảng trống (dấu cách), các ô còn lại là ''.

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

Cách Phương pháp xây dựng theo hàng

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    // Duyệt qua từng hàng i từ 0 đến a-1
    for (int i = 0; i < a; i++) {
        // Xác định số lượng cột in dấu '*' cho hàng hiện nhiên
        // Nếu hàng nằm trong vùng bị cắt (i >= a - b), chỉ in ra (a - b) cột đầu tiên
        // Ngược lại, in ra đủ a cột
        int limit = (i >= a - b) ? (a - b) : a;

        for (int j = 0; j < limit; j++) {
            cout << "*";
            if (j < limit - 1) cout << " "; // Thêm dấu cách sau dấu * nếu không phải phần tử cuối
        }

        // Nếu hàng này bị ngắn hơn a (do cắt), cần in khoảng trống ở cuối để căn chỉnh độ rộng
        // Thực tế output mẫu không yêu cầu khoảng trống ở cuối dòng, nhưng logic in.columnHeader của các giải pháp khác là in khoảng trống ở giữa.
        // Dưới đây là cách in chi tiết theo cấu trúc ô:
        for (int j = 0; j < a; j++) {
            if (j < limit) cout << "*";
            else cout << " ";
            if (j < a - 1) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(a^2)
• Space Complexity: O(1)

Hàm chính duyệt qua từng hàng i. Biến limit xác định số lượng dấu sao cần in cho hàng đó:

• Nếu hàng nằm trong vùng dưới cùng của hình vuông lớn (tức là chỉ số hàng i >= a - b), vùng này bị cắt. Do đó, số lượng dấu sao chỉ là a - b.
• Nếu hàng nằm ở trên vùng bị cắt, in đủ a dấu sao. Vòng lặp in * và thêm dấu cách ở giữa các ký tự để tạo ra hình ảnh theo yêu cầu.

Cách Phương pháp ma trận logic

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    // Duyệt qua từng ô tọa độ (i, j)
    for (int i = 0; i < a; i++) {
        for (int j = 0; j < a; j++) {
            // Kiểm tra xem ô có nằm trong vùng bị cắt không
            // Vùng cắt: hàng >= a-b và cột >= a-b
            if (i >= a - b && j >= a - b) {
                cout << " ";
            } else {
                cout << "*";
            }
            // In dấu cách sau mỗi ký tự trừ ký tự cuối cùng của hàng
            if (j < a - 1) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(a^2)
• Space Complexity: O(1)

Cách tiếp cận này mô phỏng chính xác cấu trúc grid. Nó duyệt qua từng ô (i, j) của hình vuông a x a.

• Điều kiện if (i >= a - b && j >= a - b) xác định xem ô hiện tại có nằm trong hình vuông con bị cắt (góc dưới bên phải) hay không.
• Nếu điều kiện đúng, in khoảng trống. Nếu sai, in dấu sao.
• Luôn in dấu cách sau mỗi ký tự (trừ cuối dòng) để đảm bảo định dạng.

Cách Phương pháp Logic hàng tối ưu

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (int i = 0; i < a; i++) {
        int count = (i < a - b) ? a : a - b;
        for (int j = 0; j < count; j++) {
            cout << "* ";
        }
        // In phần còn lại là khoảng trống để hàng dài bằng a (nếu cần)
        // Tuy nhiên, xét output mẫu, chúng ta chỉ cần in số lượng '*' xác định.
        // Nếu chỉ in '*' và ' ', output sẽ là:
        // * * * * *
        // ...
        // * * 
        // Dưới đây là cách in đảm bảo khoảng trống ở cuối các hàng ngắn:
        int space_count = a - count;
        for(int j = 0; j < space_count; j++) cout << "  ";
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(a^2)
• Space Complexity: O(1)

Tối ưu hóa từ phương pháp 1. Thay vì in từng ký tự, ta xác định số lượng dấu sao cần in cho mỗi hàng.

• Các hàng từ 0 đến a-b-1: in ra a dấu sao.
• Các hàng từ a-b trở lên: in ra a-b dấu sao. Để đảm bảo output trông giống một hình vuông bao gồm cả khoảng trống (như các giải pháp khác thường làm), ta có thể thêm khoảng trống ở cuối dòng. Tuy nhiên, giải pháp gốc của congtyluuthaibao1978 chỉ in số lượng '*' cần thiết và xuống dòng.

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

Bài học kinh nghiệm

• Vùng bị cắt là một hình vuông con nằm ở góc dưới bên phải với kích thước b x b.
• Các ô bị loại bỏ có tọa độ (i, j) thỏa mãn điều kiện i >= a - b và j >= a - b.
• Xử lý việc in dấu cách là quan trọng để output đúng định dạng.

Lỗi thường gặp

• Lỗi in dấu cách thừa ở cuối dòng: cout << "* " sẽ in thêm một dấu cách ở cuối dòng, có thể gây sai lệch so với bộ lọc.
• Sử dụng sai chỉ số hàng/cột (bắt đầu từ 0 hay 1): Hầu hết giải pháp dùng 0-based indexing hoặc so sánh với a-b.
• Quên in khoảng trống giữa các ký tự: Nếu chỉ in '*' liên tiếp mà không có dấu cách, output sẽ không đúng.