Hiểu bài toán

Bài toán yêu cầu xây dựng một kim tự tháp số có N tầng sao cho:

1. Tầng N (dưới cùng) có N số nguyên bất kỳ.
2. Các tầng trên (từ N-1 xuống 1) được tính bằng tổng 2 số kề bên dưới.
3. Giá trị kim tự tháp là số duy nhất ở tầng 1.
4. Ràng buộc: N ≤ 7, các số trong tháp phải có giá trị tuyệt đối ≤ 2000.

Đối với mỗi test case, đầu vào cung cấp N và giá trị V (giá trị kim tự tháp mong muốn). Đầu ra là một kim tự tháp hợp lệ có giá trị V.

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

Cách Ma trận Đơn vị (Unit Matrix)

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

int main() {
    int t; cin >> t;
    while (t--) {
        int n, v; cin >> n >> v;
        for (int i = 1; i <= n; i++) {
            cout << v << " ";
            for (int j = 2; j <= i; j++) {
                cout << 0 << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(T * N^2)
• Space Complexity: O(1)

Cách tiếp cận này dựa trên việc tạo ra các vector đơn vị. Cụ thể, ta đặt toàn bộ các số ở tầng N bằng 0, chỉ riêng một số ở vị trí đầu tiên (trái nhất) bằng V.

• Tầng N: V, 0, 0, ..., 0 (N số)
• Tầng N-1: Vì tổng 2 số bên dưới nên các số sẽ là V, 0, ..., 0 (N-1 số)
• Cứ thế lên tầng 1, ta được số V.

Cách này cực kỳ hiệu quả, chỉ cần in ra V followed by các số 0 cho mỗi hàng. Tuy nhiên, ta có thể tối ưu hơn nữa.

Cách Chuỗi 0 (Zero String)

#include <iostream>
using namespace std;

void solve() {
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; ++i) {
        cout << v << " ";
        for (int j = 2; j <= i; ++j) {
            cout << 0 << " ";
        }
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

• Time Complexity: O(T * N^2)
• Space Complexity: O(1)

Đây là biến thể của phương pháp Ma trận Đơn vị nhưng được tối ưu hóa cho việc nhập/xuất. Mô hình cốt lõi là:

• Tầng 1: V
• Tầng 2: V 0
• Tầng 3: V 0 0
• ...
• Tầng N: V 0 0 ... 0

Tất cả các số bên dưới đều là 0, nên khi cộng lên, chỉ có số đầu tiên đóng góp giá trị V. Phương pháp này đảm bảo tất cả các số đều nằm trong giới hạn cho phép (|V| ≤ 2000) và logic tính toán là chính xác.

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

Bài học kinh nghiệm

• Bài toán có tính đối xứng tuyến tính. Ta có thể sử dụng các vector đơn vị để tạo ra giá trị đầu ra.
• Giá trị của kim tự tháp phụ thuộc tuyến tính vào các giá trị ở tầng dưới cùng.
• Vì N rất nhỏ (≤ 7), ta không cần lo lắng về hiệu năng计算 quá nhiều, nhưng cách tiếp cận O(N^2) là đủ tốt.

Lỗi thường gặp

• Định dạng đầu ra: Phải in đúng N dòng cho mỗi test case, mỗi dòng có i số.
• Quên khoảng trắng hoặc newline ở cuối mỗi dòng có thể gây sai lệch.
• Lầm tưởng rằng cần phải tạo ra các số ngẫu nhiên, trong khi giải pháp Deterministic (đặc định) với V và các số 0 là đủ.