Đề bài

Sông Tô Lịch là một con sông dài và nổi tiếng ở Hà Nội. Chắc hẳn nhiều bạn đã biết, sông Tô Lịch nổi tiếng bởi hương thơm ngào ngạt, hữu xạ tự nhiên hương, luôn để lại ấn tượng khó phai trong mỗi người đi qua. Chính con sông này đã tạo cho người dân thủ đô thói quen đeo khẩu trang thường xuyên, bởi chỉ một tích tắc bỏ khẩu trang thôi, hương thơm ngây ngất sẽ ùa vào, xâm chiếm lồng ngực người đi qua, khiến cho người đi đường... ngất xỉu. Bởi thế, khi dịch COVID-19 bùng phát, người dân Hà Nội vững vàng chiến thắng đại dịch, nhờ thói quen đeo khẩu trang đã được rèn luyện từ xa xưa. Thế mới thấy, sông Tô Lịch đóng vai trò quan trọng trong công cuộc chống dịch của người dân thủ đô như thế nào.

Nằm trên tuyến đường huyết mạch của thủ đô, sông Tô Lịch có hàng chục cây cầu phục vụ nhu cầu đi qua đi lại. Tuy nhiên, đặc sản tắc đường khiến cư dân vùng ven qua sông như xông pha ra trận mạc. Để khác phục tình trạng này, người dân tạo ra một con đường qua sông mới — qua sông bằng đá. Con đường độc đạo này đảm bảo xe máy không thể đi qua, virus tắc đường không có khả năng bùng phát.

Người dân đặt n+1 hòn đá trên sông. Các hòn đá nằm trên một đường thẳng vuông góc với hai bờ. Các hòn đá lần lượt được đánh số từ 0 đến n theo thứ tự, trong đó hòn đá số 0 nằm ở một bờ và hòn đá số n nằm ở bờ bên kia. Cư dân ở đây chọn ra một số nguyên dương M, và định khoảng cách giữa hai hòn đá liên tiếp như sau: Với mỗi i thỏa mãn &0 ≤ i < n$, khoảng cách giữa hòn đá thứ i và hòn đá thứ i + 1 là .

Ví dụ, với n = 5 và M = 7, ta có , , , , .

Do mùi thơm đặc trưng của dòng sông, người dân không muốn đứng lâu giữa sông để tận hưởng cảm giác ngây ngất. Bởi thế, họ muốn qua sông với không quá j bước nhảy. Tất nhiên, mỗi bước nhảy phải xuất phát từ một hòn đá và nhảy tới hòn đá khác, bước nhảy đầu tiên phải xuất phát từ hòn đá số 0 và bước nhảy cuối cùng phải kết thúc ở hòn đá số n. Các bạn hãy giúp người dân xác định tầm nhảy tối thiểu để giúp họ qua sông. Nói cách khác, tìm số L nhỏ nhất sao cho với không quá j bước nhảy và mỗi bước nhảy có tầm xa không quá L, người dân có thể đi từ hòn đá 0 tới hòn đá n.

Input

Gồm một dòng duy nhất với ba số nguyên n, M và j $(1 ≤ j ≤ n ≤ 10^6, 1 ≤ M ≤ 10^9 + 7)$.

Output

Gồm một số duy nhất là tầm nhảy nhỏ nhất để người dân có thể qua sông sau không quá j bước nhảy.

Nhận xét:

• Giả sử với độ dài lớn nhất của mỗi bước nhảy là L thì có thể nhảy hết qua các hòn đá thì tương tự với L + 1, L + 2,... thì cũng có thể nhảy hết qua các hòn đá. Vì vậy, ta sử dụng kĩ thuật chia nhị phân để chuyển bài toán từ bài toán tối ưu về bài toán kiểm tra.

Hàm chia nhị phân:

#define INF (long long)1e16

long long solve(void) {
    long long L = 1, R = INF, mid;
    while (true) {
        if (L == R) return L;
        if (R - L == 1) return check(L) ? L : R;
        mid = (R + L) >> 1;
        if (check(mid) == true) R = mid;
        else L = mid + 1;
    }
}

Giải thích:

• Ta gọi khoảng $[L, R]$ là khoảng nghi ngờ chứa kết quả của bài toán.
• $mid = (R + L) >> 1$, đây là phép toán dịch bit phải, tương đương với $mid = (R + L)/2$ nhưng vì phép dịch bit có tốc độ xử lí nhanh hơn phép chia thông thường nhiều nên ta giữ nguyên.
• Khi $check(mid) = true$, tức là mid có là kết quả của bài toán (có thể chưa được tối ưu), theo nhận xét ở trên thì với $mid + 1$, $mid + 2$ đều có thể vượt qua hết các hòn đá, tuy nhiên, mục tiêu của chúng ta là tìm kết quả nhỏ nhất nên ta sẽ cho $R = mid$, khi đó khoảng nghi ngờ có nghiệm sẽ là $[L, mid]$, giả sử kết quả mid đã tối ưu thì nó vẫn nằm trong khoảng nghiệm đang xét.
• Khi $check(mid) = false$, tức là mid không phải là kết quả của bài toán, suy ra $mid - 1$, $mid - 2$,.. cũng không thể là kết quả của bài toán, vì vậy ta sẽ cho $L = mid + 1$, khoảng nghi ngờ có nghiệm sẽ trở thành $[mid + 1, R]$.
• Khi $L = R$, khoảng nghiệm nghi ngờ là $[L, L] = {L}$, lẽ dĩ nhiên L là nghiệm của bài toán và là nghiệm tối ưu.
• Khi $R - L = 1$, khoảng nghiệm nghi ngờ là $[L, L + 1] = {L, L + 1}$, khi đó ta ưu tiên kiểm tra $L$ trước bởi kết quả phải là nhỏ nhất, nếu $L$ không phải là nghiệm thì chắc chắn $R = L + 1$ là nghiệm tối ưu của bài toán.

Hàm kiểm tra kết quả:

int d[1000005], m, limit, n;

//d[i] là khoảng cách từ viên đá thứ i-1 đến viên đá thứ i.
//limit là số bước nhảy lớn nhất.
//n là số viên đá.
//mục tiêu của hàm là kiểm tra xem dist có phải là kết quả của bài toán hay không

bool check(long long dist) {
    int i = 0;
    long long tmp  = 0;
    for (int j = 1; j<= limit; j++) {
        int k = i;
        tmp = 0;
        while (k < n && tmp + d[k+1] <= dist) {
            tmp += d[k+1];
            k++;
        }
        i = k;
        if (i == n) return true;
    }
    return false;
}

Giải thích:

• Ta sử dụng tham lam: Với mỗi lần nhảy, ta sẽ tìm vị trí của viên đã mà ta có thể nhảy đến xa nhất thoả mãn điều kiện khoảng cách đó nhỏ hơn $dist$.
• Ta gọi vị trí ban đầu là $i = 0$.
• Biến $tmp$ sẽ lưu khoảng cách mà ta đã nhảy khi đi qua từng hòn đá, điều kiện là khoảng cách ấy phải nhỏ hơn $dist$ tức là nhỏ hơn giá trị đang kiểm tra.
• Nếu có thể nhảy từ hòn đá thứ k đến hòn đá thứ $k + 1$, ta cần cộng thêm khoảng cách từ viên đá thứ $k + 1$ đến viên đá thứ $k$ vào biến $tmp$, tức là $d[k+1]$, và tăng vị trí hiện tại là $k$ thêm $1$ đơn vị, với điều kiện là $k < n$, tức là chưa đến đích.
• Nếu $i = n$, thể hiện vị trí hiện tại là $n$ (đích đến) nên $dist$ là một kết quả của bài toán (có thể chưa tối ưu), hàm check trả về giá trị $true$.
• Nếu sau $limit$ lần lặp lại việc nhảy mà hàm vẫn chưa trả về giá trị $true$, tức là không thể nhảy đến đích trong $limit$ lần, hàm check trả về giá trị là $false$ (không phải là kết quả của bài toán).

Full code:

#include <bits/stdc++.h>
#define INF (long long)1e16
using namespace std;
int d[1000005], m, limit, n;
bool check(long long dist) {
    int i = 0;
    long long tmp  = 0;
    for (int j = 1; j<= limit; j++) {
        int k = i;
        tmp = 0;
        while (k < n && tmp + d[k+1] <= dist) {
            tmp += d[k+1];
            k++;
        }
        i = k;
        if (i == n) return true;
    }
    return false;
}

long long solve(void) {
    long long L = 1, R = INF, mid;
    while (4 < 5) {
        if (L == R) return L;
        if (R - L == 1) return check(L) ? L : R;
        mid = (R + L) >> 1;
        if (check(mid) == true) R = mid;
        else L = mid + 1;
    }
}

int main()
{
    freopen("river.inp", "r", stdin); //Đọc input từ file river.inp
    freopen("river.out", "w", stdout); //In ra output tại file river.out
    long long ll = 1;
    cin >> n >> m >> limit;

    //Tính d[i] theo công thức đã cho ở đầu bài, nhắc lại, d[i] là khoảng cách từ hòn đá thứ i-1 đến hòn đá thứ i.
    for (int i = 1; i<=n; i++)
        d[i] = 1 + (ll*(i-1)*(i-1))%m;  

    cout << solve(); //In ra kết quả.
    return 0;
}

Lưu ý:

• Bởi giới hạn của bài toán là $n <= 10^6$ nên khi chạy đến $n$ thì $(i-1)*(i-1)$ sẽ lớn hơn phạm vi giá trị của kiểu int, khi đó ta có thể khắc phục bằng cách đổi kiểu dữ liệu của $i$ từ kiểu int thành kiểu long long hoặc viết như trên để tránh việc bị tràn số.

Nguồn bài tập: Phạm Văn Hạnh.

Thiết kế thuật giải: Ấn vào đây.