Hiểu bài toán

Một con ốc sên muốn trèo lên một cái cây cao V mét. Mỗi ngày nó trèo lên được A mét, nhưng mỗi đêm lại trèo xuống B mét. Nhiệm vụ là tìm số ngày tối thiểu để con ốc sên reaches (đến được) đỉnh cây. Với điều kiện 1 ≤ B < A ≤ 10^9 và 1 ≤ V ≤ 10^9.

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

Cách Mô phỏng (Simulation)

#include <iostream>
using namespace std;

int main() {
    long long A, B, V;
    cin >> A >> B >> V;

    long long current = 0;
    long long days = 0;

    while (current < V) {
        days++;
        current += A; // leo lên vào ban ngày
        if (current >= V) break;
        current -= B; // trượt xuống vào ban đêm
    }

    cout << days << endl;
    return 0;
}

• Time Complexity: O(V / (A - B))
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất, mô phỏng quá trình trèo của con ốc sên từng ngày. Vòng lặp tiếp tục cho đến khi độ cao hiện tại >= V. Tuy nhiên, do V, A, B có thể lên tới 10^9, độ phức tạp thời gian là không thể chấp nhận được (quá chậm)

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

#include <iostream>
using namespace std;

int main() {
    long long A, B, V;
    cin >> A >> B >> V;

    long long days;
    if (A >= V) {
        days = 1;
    } else {
        // V - A là phần còn lại sau ngày đầu tiên
        // (A - B) là khoảng cách leo net mỗi ngày
        // ceil((V - A) / (A - B)) là số ngày sau ngày đầu tiên
        days = 1 + (V - A + (A - B) - 1) / (A - B);
    }

    cout << days << endl;
    return 0;
}

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

Phân tích bài toán:

1. Nếu A >= V, ốc sên chỉ mất 1 ngày.
2. Nếu A < V, sau ngày đầu tiên, ốc sên ở độ cao A - B (vì trượt xuống B).
3. Từ ngày thứ 2 trở đi, mỗi ngày net gain là A - B.
4. Ta cần tìm số ngày để弥补 phần còn lại (V - A).
5. Số ngày cần thêm là ceil((V - A) / (A - B)).
6. Tổng số ngày là 1 + ceil((V - A) / (A - B)). Công thức có thể viết gọn: days = 1 + (V - A + (A - B) - 1) / (A - B).

Cách Công thức tối ưu (Optimized Formula)

#include <iostream>
using namespace std;

int main() {
    long long A, B, V;
    cin >> A >> B >> V;

    // days = 1 + (V - A + A - B - 1) / (A - B)
    //      = 1 + (V - B - 1) / (A - B)
    long long days = 1 + (V - B - 1) / (A - B);

    cout << days << endl;
    return 0;
}

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

Đây là phiên bản tối ưu hóa của công thức toán học. Thay vì tách trường hợp A >= V, ta có thể dùng một công thức duy nhất:

• Xét việc leo của ốc sên: Vào ngày thứ n, ốc sên sẽ ở độ cao nA - (n-1)B = n*(A-B) + B.
• Ta cần tìm n nhỏ nhất sao cho n*(A-B) + B >= V.
• Suy ra: n*(A-B) >= V - B
• n >= (V - B) / (A - B)
• Do n phải là số nguyên, n = ceil((V - B) / (A - B))
• Dùng công thức chia lấy trần: n = (V - B + (A - B) - 1) / (A - B) = (V - B - 1) / (A - B) + 1. Đây là cách hiệu quả nhất và xử lý đúng tất cả các trường hợp.

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

Bài học kinh nghiệm

• Bài toán có thể chuyển đổi từ mô phỏng sang công thức toán học để giảm độ phức tạp từ O(V) xuống O(1).
• Cần phân biệt giữa 'leo lên nhưng chưa vượt qua đỉnh' và 'đạt được đỉnh'. Vào ngày cuối cùng, ốc sên chỉ cần leo đủ A mét để chạm đỉnh, không cần phải trượt xuống.
• Công thức tối ưu nhất là days = 1 + (V - B - 1) / (A - B), giúp xử lý gọn các trường hợp A >= V và A < V trong cùng một biểu thức.

Lỗi thường gặp

• Sử dụng biến có kiểu int thay vì long long hoặc equivalent, dẫn đến overflow khi V, A, B lên tới 10^9.
• Viết sai công thức toán học, ví dụ quên cộng thêm 1 ngày, hoặc không xử lý đúng phép chia lấy trần (ceiling division) với số nguyên.
• Không xử lý trường hợp đặc biệt khi A >= V (ốc sên chỉ mất 1 ngày), dẫn đến chia cho 0 hoặc kết quả sai nếu dùng công thức chung mà không kiểm tra.