Hiểu bài toán

Bài toán mô phỏng sự tăng trưởng của một loại cây có chu kỳ sinh trưởng 2 mùa (xuân và hè) trong một năm. Cây bắt đầu với chiều cao là 1 mét. Yêu cầu tính chiều cao của cây sau n lần sinh trưởng. Vào các lần sinh trưởng lẻ (1, 3, 5,...), tức là mùa xuân, cây tăng chiều cao gấp đôi. Vào các lần sinh trưởng chẵn (2, 4, 6,...), tức là mùa hè, cây tăng chiều cao thêm 1 mét. Với n nhỏ (≤ 60), ta có thể mô phỏng trực tiếp quá trình này.

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

Cách Mô phỏng trực tiếp (Simulation)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        long long h = 1; // Chiều cao ban đầu
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) { // Lần sinh trưởng lẻ (Mùa xuân)
                h *= 2;
            } else { // Lần sinh trưởng chẵn (Mùa hè)
                h += 1;
            }
        }
        cout << h << "\n";
    }
    return 0;
}

• Time Complexity: O(n) với mỗi test case, tổng thể O(t * n). Với n ≤ 60 thì rất nhanh.
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Ta bắt đầu với chiều cao ban đầu h = 1. Với mỗi lần sinh trưởng từ 1 đến n, ta kiểm tra xem đó là lần sinh trưởng lẻ hay chẵn. Nếu là lẻ (i % 2 != 0), ta nhân đôi chiều cao (h = h * 2). Nếu là chẵn, ta cộng thêm 1 vào chiều cao (h = h + 1). Kết quả cuối cùng chính là chiều cao sau n lần sinh trưởng. Với n tối đa là 60, số lần lặp là hoàn toàn chấp nhận được.

Cách Công thức toán học (Mathematical Formula)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        // Chiều cao sau n lần sinh trưởng là: 2^(số lần xuân) + (số lần hè)
        // Số lần xuân = ceil(n / 2.0)
        // Số lần hè = floor(n / 2.0)
        long long num_spring = (n + 1) / 2; // Số lần sinh trưởng lẻ
        long long num_summer = n / 2;       // Số lần sinh trưởng chẵn
        long long h = (1LL << num_spring) + num_summer;
        cout << h << "\n";
    }
    return 0;
}

• Time Complexity: O(1) với mỗi test case.
• Space Complexity: O(1)

Ta có thể quan sát quy luật toán học thay vì mô phỏng. Gọi k là số lần sinh trưởng lẻ (mùa xuân) và m là số lần sinh trưởng chén (mùa hè).

• Nếu n là số chẵn: k = n/2, m = n/2. Chiều cao ban đầu là 1. Sau k lần nhân đôi, chiều cao là 1 * 2^k. Sau đó, m lần cộng 1, chiều cao là 2^k + m.
• Nếu n là số lẻ: k = (n+1)/2, m = (n-1)/2. Chiều cao sau k lần nhân đôi là 2^k. Sau đó m lần cộng 1, chiều cao là 2^k + m. Nhận thấy với cả hai trường hợp, số lần xuân là (n + 1) / 2 (kiểu số nguyên), số lần hè là n / 2. Do đó, công thức tổng quát là: Height = 2^((n+1)/2) + n/2. Cách này bỏ qua vòng lặp, chạy nhanh hơn hẳn.

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

Bài học kinh nghiệm

• Bài toán có tính chất chu kỳ theo cặp (Xuân, Hè). Lần sinh trưởng lẻ là nhân đôi, chẵn là cộng 1.
• Với n nhỏ (≤ 60), ta có thể mô phỏng dễ dàng mà không lo tràn số nếu dùng long long (vì 2^30 đã rất lớn, 2^60 nằm trong giới hạn của long long).
• Có thể rút gọn quy luật thành công thức toán học để giải quyết ngay lập tức mà không cần vòng lặp.

Lỗi thường gặp

• Quên khởi tạo chiều cao ban đầu là 1 (nếu để 0 hoặc không gán, kết quả sai).
• Sử dụng biến có kiểu dữ liệu quá nhỏ (như int) cho chiều cao. Mặc dù 2^60 (~10^18) nằm trong giới hạn của long long (khoảng 9 * 10^18), nhưng nó vượt quá giới hạn của int (khoảng 2 * 10^9). Nên dùng long long cho biến lưu chiều cao.
• Sai logic kiểm tra mùa xuân/mùa hè (ví dụ dùng i % 2 == 0 cho mùa xuân).