Editorial for lonhon: Lớn hơn

Hiểu bài toán

Bài toán mô phỏng sự tăng trưởng của hai cây A và B. Cây A tăng chiều cao gấp 3 lần mỗi năm, cây B tăng gấp 2 lần mỗi năm. Cho chiều cao ban đầu A và B, cần tìm số năm tối thiểu để A cao hơn B. Với A, B <= 10, ta có thể mô phỏng trực tiếp cho đến khi A > B.

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

Cách Mô phỏng vòng lặp (Brute Force)

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int years = 0;
    while (a <= b) {
        a *= 3;
        b *= 2;
        years++;
    }
    printf("%d\n", years);
    return 0;
}

• Time Complexity: O(log B) - Số lần lặp phụ thuộc vào tỷ lệ tăng trưởng, rất nhỏ với giới hạn đề bài.
• Space Complexity: O(1)

Sử dụng vòng lặp while để mô phỏng từng năm. Trong mỗi năm, nhân chiều cao hiện tại của A với 3 và của B với 2, đồng thời tăng biến đếm năm. Vòng lặp dừng lại khi chiều cao của A lớn hơn B. Đây là cách tiếp cận trực quan nhất.

Cách Mô phỏng với kiểm tra ban đầu

#include <stdio.h>
#include <stdlib.h> 

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    if(a > b) {
        printf("0");
        return 0;
    }
    for(int i = 1; ; i++){
        a *= 3;
        b *= 2;
        if(a > b) {
            printf("%d", i);
            break;
        }
    }
    return 0;
}

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

Giải pháp này tối ưu hóa một chút bằng cách kiểm tra ngay từ đầu xem A đã lớn hơn B hay chưa. Nếu có, in ra 0 và kết thúc. Ngược lại, dùng vòng lặp for vô điều kiện để mô phỏng và break khi điều kiện thỏa mãn.

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

Bài học kinh nghiệm

• Vì giới hạn A, B rất nhỏ (<= 10), số năm cần mô phỏng là rất ít (thường dưới 10 năm), nên giải thuật mô phỏng là hoàn toàn đủ dùng và hiệu quả.
• Biến years nên được khởi tạo là 0 và tăng trước khi nhân hoặc khởi tạo là 1 và tăng sau khi nhân, miễn là logic nhất quán và đúng với yêu cầu 'sau bao nhiêu năm'.

Lỗi thường gặp

• Lỗi logic số năm: In ra giá trị của biến đếm sai thời điểm (ví dụ: in ra giá trị trước khi increment hoặc sau khi break).
• Quên xử lý trường hợp đặc biệt: Nếu A > B ngay từ đầu, đáp án phải là 0.