Hiểu bài toán

Bài toán mô phỏng việc đổ nước vào một hệ thống đĩa xếp chồng lên nhau. Đĩa 1 có dung tích a, và mỗi đĩa sau có dung tích tăng thêm b so với đĩa trước nó. Dung tích của đĩa thứ i là a + (i-1)*b. Khi đổ N lít nước vào đĩa 1, nước sẽ tràn qua các đĩa bên dưới theo thứ tự. Yêu cầu là找出 số lượng đĩa chứa nước (tức là có ít nhất một chút nước) sau khi đổ hết N lít nước. Do N có thể lên tới 10^18, ta cần một thuật toán hiệu quả.

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

Cách Tìm kiếm nhị phân (Binary Search)

#include <iostream>
using namespace std;

typedef long long ll;

// Hàm kiểm tra xem k đĩa đầu tiên có chứa được hết N lít nước không
bool can(ll k, ll n, ll a, ll b) {
    // Tránh tràn số khi tính k*b
    if (b != 0 && k > (2e18 / b)) return false;
    // Sử dụng __int128 để tránh tràn số khi tính tổng
    __int128 sum = (__int128)k * a + (__int128)b * k * (k - 1) / 2;
    return sum <= n;
}

int main() {
    ll n, a, b;
    cin >> n >> a >> b;

    ll l = 0, r = 2e9, ans = 0;
    // Tìm số lượng đĩa có thể chứa đầy nước hoàn toàn
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (can(mid, n, a, b)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    // Số đĩa có nước = số đĩa đầy + 1 (đĩa thứ ans+1 chứa phần nước còn lại)
    cout << ans + 1 << endl;
    return 0;
}

• Time Complexity: O(log(10^9)) ~ O(30)
• Space Complexity: O(1)

Hành vi của hệ thống là các đĩa đầu tiên sẽ được đổ đầy nước hoàn toàn trước khi nước tràn sang đĩa tiếp theo. Nếu tổng dung tích của k đĩa đầu tiên nhỏ hơn hoặc bằng N, thì chắc chắn k đĩa này đều chứa nước. Ta có thể sử dụng tìm kiếm nhị phân để tìm số lượng đĩa lớn nhất có thể chứa đầy nước hoàn toàn (k). Công thức tổng dung tích của k đĩa là tổng của một cấp số cộng: S = ka + bk*(k-1)/2. Do N rất lớn, ta phải dùng biến 128-bit (__int128) để tính toán tổng dung tích tránh tràn số. Đĩa thứ k+1 sẽ chứa phần nước còn lại (nếu có), do đó tổng số đĩa có nước là k+1.

Cách Giải phương trình bậc 2 (Công thức lượng giác)

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

typedef long long ll;

int main() {
    ll n, a, b;
    cin >> n >> a >> b;

    // Xử lý trường hợp đặc biệt khi b = 0
    if (b == 0) {
        cout << (n + a - 1) / a << endl;
        return 0;
    }

    // Công thức tổng quát: b/2 * k^2 + (a - b/2) * k >= n
    // Ta có thể dùng công thức nghiệm của phương trình bậc 2 để tìm k xấp xỉ
    // k = [-(a - b/2) + sqrt((a - b/2)^2 + 4 * (b/2) * n)] / b
    // Tuy nhiên, cần xử lý số thực cẩn thận và kiểm tra lại do sai số.

    double A = b / 2.0;
    double B = a - b / 2.0;
    double C = -n;

    double delta = B*B - 4*A*C;
    double k = (-B + sqrt(delta)) / (2*A);

    // Kết quả là số nguyên lớn nhất nhỏ hơn hoặc bằng k + 1 (do công thức bài toán)
    // Tuy nhiên, cách này dễ sai số. Solution 3 trong bài nộp là:
    // cout << ceil((-(a - b/2) + sqrt((a-b/2)*(a-b/2) + 4*v*(b/2)) ) / b);
    // Điều này cho thấy họ đang tìm số mũ k sao cho tổng >= N.

    // Để an toàn, ta dùng hàm ceil và ép kiểu cẩn thận
    ll ans = ceil((-(double)a + b/2.0 + sqrt((double)(a-b/2.0)*(a-b/2.0) + 4.0*n*(b/2.0))) / b);
    // Lấy max(1, ans) vì ít nhất 1 đĩa
    cout << max(1LL, ans) << endl;

    return 0;
}

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

Đây là cách tiếp cận toán học trực tiếp. Tong dung tích sau k đĩa là S(k) = ka + bk(k-1)/2. Ta cần tìm số nguyên dương k nhỏ nhất sao cho S(k) >= N. Biến đổi phương trình ta được: (b/2)k^2 + (a - b/2)*k - N >= 0. Đây là một phương trình bậc 2 theo k. Ta có thể giải nghiệm theo công thức lượng giác. Tuy nhiên, do giới hạn precision của số thực double, cách này có thể bị sai số đối với các giá trị lớn (đặc biệt khi N lên tới 10^18). Solution 3 trong bài nộp là một ví dụ về cách tiếp cận này.

Cách Tìm kiếm nhị phân không dùng __int128 (Binary Search)

#include <iostream>
using namespace std;

typedef long long ll;

ll n, a, b;

// Kiểm tra xem k đĩa đầu tiên có chứa được n lít nước không
// Sử dụng so sánh trực tiếp để tránh tràn số
bool check(ll k) {
    // Tính tổng dung tích: S = k*a + b*k*(k-1)/2
    // Kiểm tra điều kiện: S >= n

    // Phép chia (k*(k-1))/2 có thể gây tràn số nếu k lớn.
    // Ta cần kiểm tra từng phần.

    // So sánh: k*a + b*k*(k-1)/2 >= n
    // => b*k*(k-1) >= 2*(n - k*a)

    ll rhs = 2 * (n - k * a);
    if (rhs < 0) return true; // Đĩa 1 đã quá n

    // Tính lhs = b * k * (k - 1)
    // Cần kiểm tra tràn số trước
    if (k > 2e9) return false; // k quá lớn, aprox limit

    ll lhs = b * k * (k - 1);

    return lhs >= rhs;
}

int main() {
    cin >> n >> a >> b;
    ll l = 1, r = 2e9, ans = 0;

    while (l <= r) {
        ll mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(log(10^9))
• Space Complexity: O(1)

Đây là biến thể của phương pháp tìm kiếm nhị phân. Thay vì tính chính xác tổng dung tích (có thể vượt quá 64-bit), ta biến đổi phương trình bất đẳng thức để kiểm tra điều kiện. Ta cần tìm số k nhỏ nhất sao cho tổng dung tích >= N. Bằng cách nhân 2 cả vế, ta được: 2ka + bk(k-1) >= 2N. Ta có thể kiểm tra điều kiện này trực tiếp bằng các phép tính 64-bit. Tuy nhiên, ta vẫn cần cẩn thận với việc tràn số trong phép nhân bk*(k-1). Do b <= 10 và k tìm được tối đa khoảng 10^9, phép nhân này có thể vượt quá 2^63-1. Do đó, cách an toàn nhất vẫn là dùng __int128 như Solution 1.

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

Bài học kinh nghiệm

• Hệ thống hoạt động như một bình chứa: các đĩa dưới sẽ chỉ nhận nước khi đĩa trên đã đầy. Do đó, có một số nguyên k các đĩa đầu tiên được lấp đầy hoàn toàn, và đĩa thứ k+1 chứa phần nước còn lại.
• Tổng dung tích của k đĩa tạo thành một cấp số cộng: S(k) = ka + bk*(k-1)/2. Bài toán quy về việc tìm k lớn nhất sao cho S(k) <= N.
• Do N có thể lên tới 10^18, các phép tính cần sử dụng số nguyên 128-bit (__int128) hoặc các kỹ thuật tránh tràn số để đảm bảo độ chính xác.

Lỗi thường gặp

• Tràn số (Integer Overflow): Khi tính tổng dung tích, các số như bk(k-1) có thể vượt quá giới hạn của kiểu long long (64-bit). Cần sử dụng __int128 hoặc kỹ thuật chia/so sánh.
• Sai số số học dấu phẩy động (Floating Point Error): Cách giải phương trình bậc 2 dùng số thực double có thể bị sai lệch đối với số lớn, dẫn đến kết quả sai.
• Lỗi logic off-by-one: Cần phân biệt rõ giữa số đĩa đầy nước hoàn toàn và số đĩa chứa nước. Đĩa thứ k+1 luôn chứa nước nếu N > S(k), nên kết quả thường là k+1.