Hiểu bài toán

Cho hai số nguyên dương a và b (1 ≤ a ≤ b ≤ 1000). Ban đầu tờ giấy có độ dày a. Mỗi lần gấp đôi, độ dày tăng lên gấp đôi (a, 2a, 4a, 8a,...). Tìm số lần gấp ít nhất để độ dày tờ giấy không vượt quá b, nhưng đồng thời khiến cho độ dày mới lớn nhất có thể (gần b nhất) để giảm thiểu gập ghềnh. Nói cách khác, tìm số lần gấp k sao cho a * 2^k ≤ b và a * 2^(k+1) > b.

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

Cách Lặp (Simulation)

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int count = 0;
    // Lặp khi gấp đôi vẫn không vượt quá b
    while (a * 2 <= b) {
        a *= 2;
        count++;
    }
    cout << count;
    return 0;
}

• Time Complexity: O(log(b/a))
• Space Complexity: O(1)

Phương pháp này mô phỏng chính xác quá trình gấp giấy. Ta bắt đầu với độ dày a và lặp lại việc nhân đôi độ dày (a *= 2) chừng nào độ dày mới vẫn nhỏ hơn hoặc bằng b. Biến đếm count sẽ tăng lên mỗi khi thực hiện một bước gấp. Vòng lặp dừng lại khi a * 2 > b, lúc này count chính là số lần gấp tối đa có thể thực hiện mà không vượt quá b.

Cách Sử dụng Logarit

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double a, b;
    cin >> a >> b;
    // Tính logarit cơ số 2 của tỉ lệ b/a
    int ans = floor(log2(b / a));
    cout << ans;
    return 0;
}

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

Đây là phương pháp toán học. Số lần gấp k cần tìm thỏa mãn điều kiện: a * 2^k ≤ b. Chia cả hai vế cho a, ta được 2^k ≤ b/a. Lấy logarit cơ số 2, ta có k ≤ log2(b/a). Vì k là số nguyên, ta lấy phần nguyên của log2(b/a). Cách này tính toán trực tiếp số lần gấp mà không cần vòng lặp.

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

Bài học kinh nghiệm

• Bài toán yêu cầu tìm số mũ k lớn nhất sao cho a * 2^k ≤ b.
• Điều này tương đương với việc tìm phần nguyên của logarit cơ số 2 của tỉ lệ b/a.

Lỗi thường gặp

• Sử dụng biến số nguyên (int) cho a khi tính toán giá trị a * 2 có thể gây tràn số (overflow) nếu a lớn, nhưng với ràng buộc a, b ≤ 1000 thì cách này vẫn an toàn.
• Nếu sử dụng phép chia整数 (integer division) thay vì logarit, cần đảm bảo logic tính toán chính xác số lần gấp tối đa.