Editorial for dancing: Văn nghệ chào mừng

Hiểu bài toán

Bài toán yêu cầu tính số lượng học sinh mặc trang phục xanh (nằm ở viền ngoài) và đỏ (nằm bên trong) để tạo thành một hình tam giác có chiều cao h. Dựa vào các mẫu minh họa, ta thấy:

• Số học sinh xanh tạo thành hình tam giác rỗng.
• Số học sinh đỏ tạo thành hình tam giác đặc bên trong.

Với chiều cao h:

• Dưới cùng là 1 học sinh xanh.
• Lớp trên cùng (đỉnh) là 1 học sinh xanh.
• Các lớp ở giữa có số lượng xanh tăng dần và số lượng đỏ tăng dần.

Quan sát:

• Số lượng học sinh xanh: Ta có thể tính bằng tổng chu vi của các hình vuông/viền. Với h=4, viền là 12. Với h=5, viền là 16. Quan hệ là $4h - 4$.
• Số lượng học sinh đỏ: Đây là phần bên trong của tam giác. Với h=4, bên trong là 4. Với h=5, bên trong là 9. Quan hệ là $(h-2)^2$.

Đầu vào h có thể lên tới $10^6$, do đó cần sử dụng kiểu dữ liệu 64-bit (long long) để tránh tràn số khi tính $h^2$ hoặc $4h$.

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

Cách Công thức trực tiếp

#include <stdio.h>

int main() {
    long long h;
    scanf("%lld", &h);

    // Số học sinh xanh (viền tam giác)
    // Công thức: 4*h - 4
    long long blue = 4 * h - 4;

    // Số học sinh đỏ (phần bên trong)
    // Công thức: (h-2)^2
    long long red = (h - 2) * (h - 2);

    printf("%lld %lld", blue, red);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất. Dựa vào quan sát hình học:

1. Hình tam giác có chiều cao h có thể xem là một hình vuông lớn bị cắt góc.
2. Số lượng học sinh xanh là chu vi của hình vuông có cạnh h trừ đi 4 góc (vì các góc trên/dưới chỉ có 1 người).
   • Chu vi hình vuông cạnh h là 4h.
   • Trừ đi 4 góc thừa: 4h - 4 = 4(h-1).
3. Phía bên trong viền xanh là một hình tam giác rỗng (hoặc hình vuông đặc) có chiều cao h-2.
   • Số lượng học sinh đỏ chính là diện tích của hình vuông có cạnh h-2, tức là $(h-2)^2$.
4. Với h=10^6, kết quả nằm trong khoảng $10^{12}$, bắt buộc dùng long long.

Cách Mô phỏng t tổng quan (Công thức tổng quát)

#include <stdio.h>

int main() {
    long long n;
    scanf("%lld", &n);

    // Xanh: n^2 - (n-2)^2 = 4n - 4
    // Đỏ: (n-2)^2

    long long x = n*n - (n-2)*(n-2);
    long long y = (n-2)*(n-2);

    printf("%lld %lld", x, y);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này cũng dựa trên công thức nhưng giải thích theo cách xem tam giác là một hình vuông đặc.

• Tổng số học sinh nếu xếp đầy một hình vuông cạnh h là $h^2$.
• Nếu ta chỉ lấy viền ngoài, số lượng sẽ là tổng số trừ đi phần bên trong.
• Phần bên trong (màu đỏ) là một hình vuông cạnh h-2, diện tích $(h-2)^2$.
• Số lượng xanh = $h^2 - (h-2)^2$.
• Giải nén công thức: $h^2 - (h^2 - 4h + 4) = 4h - 4$. Kết quả tương đương với cách 1.

Cách Mô phỏng lặp (Đối với h nhỏ)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    long long red = 0;
    long long blue = 0;

    // Duyệt qua từng hàng
    // Với hàng i (từ 1 đến n):
    // - Nếu là hàng 1 hoặc hàng n: 1 xanh
    // - Nếu là hàng 2 hoặc hàng n-1: 1 xanh + 1 đỏ + 1 xanh (tổng 3 xanh, 1 đỏ)
    // - Các hàng còn lại: logic tương tự nhưng số lượng đỏ tăng dần

    // Tuy nhiên, cách này chậm với n lớn, nên chỉ dùng để kiểm chứng logic nhỏ.
    // Code minh họa logic tính tay:

    // Số lượng đỏ: tổng của các số lẻ từ 1 đến (n-3) * 2 + 1? 
    // Thực tế: Với h=4, đỏ là 1+3 = 4. Với h=5, đỏ là 1+3+5 = 9.
    // Quy luật: Số đỏ ở hàng k (từ 3 đến n-1) là 2*(k-2)-1.
    // Tổng đỏ = (n-2)^2.

    // Code lặp thực sự (chậm):
    for (int i = 1; i <= n; i++) {
        if (i == 1 || i == n) {
            blue += 1;
        } else if (i == 2 || i == n - 1) {
            blue += 2; // 2 bên viền
            red += 1;
        } else {
            // Các hàng ở giữa
            // Số đỏ: 2*(i-2)-1
            // Số xanh: 2 (hai bên viền)
            blue += 2;
            red += (2 * (i - 2) - 1);
        }
    }

    printf("%lld %lld", blue, red);
    return 0;
}

• Time Complexity: O(h)
• Space Complexity: O(1)

Đây là cách tiếp cận mô phỏng lại quy trình xếp hình.

• Chúng ta duyệt qua từng hàng từ 1 đến h.
• Nếu là hàng đầu/cuối (i=1 hoặc i=h): Chỉ có 1 người xanh.
• Nếu là hàng thứ 2 hoặc hàng thứ h-1: Có 2 người xanh (đầu và cuối hàng) và 1 người đỏ ở giữa.
• Các hàng còn lại: Cứ 2 người xanh ở hai đầu và số người đỏ ở giữa tăng dần (1, 3, 5, ...).
• Tính toán:
  • Xanh: $1 + 2 + 2 + ... + 2 + 1 = 4h - 4$.
  • Đỏ: $1 + 3 + 5 + ... + (2(h-3)+1) = (h-2)^2$. Phương pháp này có độ phức tạp tuyến tính O(h), không khả thi với h lên tới $10^6$ (cần O(1)), nhưng giúp hiểu rõ cấu trúc bài toán.

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

Bài học kinh nghiệm

• Bài toán có thể quy về các công thức toán học đơn giản thay vì mô phỏng trực tiếp.
• Số lượng học sinh đỏ tạo thành một hình vuông có cạnh là h-2, do đó số lượng là $(h-2)^2$.
• Số lượng học sinh xanh là chu vi của hình vuông cạnh h trừ đi 4 góc, hoặc hiệu của hai bình phương: $h^2 - (h-2)^2 = 4h - 4$.
• Với giới hạn h <= $10^6$, kết quả có thể lên tới $10^{12}$, bắt buộc phải dùng kiểu long long (64-bit integer).

Lỗi thường gặp

• Sử dụng kiểu int (32-bit) dẫn đến tràn số (overflow) khi h lớn (ví dụ h=10^6 thì 4h = 4,000,000 < 2^31, nhưng nếu tính h*h = $10^{12}$ thì chắc chắn tràn).
• Hiểu sai quy luật màu sắc: Nhầm lẫn số lượng xanh và đỏ.
• Với h=3, hình mẫu là: * +

Số xanh = 8, Số đỏ = 1. Áp dụng công thức: Xanh = 4*3-4=8, Đỏ = (3-2)^2=1. Đúng.