Hướng dẫn cho Du lịch


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

\(n\) người cần đi từ biển về khách sạn quãng đường dài \(l\). Mỗi người đi bộ tốc độ \(v_1\). Có 1 xe chở tối đa \(k\) người mỗi chuyến, chạy tốc độ \(v_2\) (\(v_2>v_1\)). Mỗi người được lên xe nhiều nhất 1 lần (có thể đi bộ phần còn lại). Xe có thể quay lại đón nhóm khác. Hỏi thời gian nhỏ nhất để tất cả về đến khách sạn (sai số \(\le 10^{-6}\)).

Phân tích

  • Điểm mấu chốt: xe nhanh hơn người đi bộ, nên chiến lược tối ưu là:
    • Xe chở một nhóm \(k\) người tiến về phía khách sạn một đoạn, thả họ xuống để họ tự đi bộ nốt.
    • Xe quay lại (đi ngược chiều) để gặp nhóm tiếp theo (đang đi bộ từ điểm xuất phát).
  • Vì mỗi người chỉ lên xe 1 lần nên xe không thể “chuyển tiếp” nhiều lần cho cùng một người; mỗi người thuộc đúng một nhóm được chở.
  • Số nhóm cần chở là:
\[m = \left\lceil \frac{n}{k} \right\rceil\]
  • Mô hình hóa theo “thời gian hoàn thành”: nếu sau khi xe thực hiện \(m\) lần chở (lần cuối không cần quay lại), ta có thể tính được thời điểm muộn nhất mà một người về khách sạn.
  • Bài toán chuẩn (rất hay gặp) giải được bằng cách giả sử lời giải là \(T\) và kiểm tra có thể hoàn thành trong \(T\) hay không (nhị phân trên đáp án).

Hướng giải quyết

Ý tưởng kiểm tra (feasibility) với thời gian \(T\)

Gọi \(x\) là khoảng cách (tính từ điểm xuất phát) mà xe chở một nhóm trước khi thả họ xuống. Nếu nhóm được thả tại vị trí \(x\) thì:

  • Thời gian nhóm đó ngồi xe: \(\dfrac{x}{v_2}\)
  • Quãng còn lại họ đi bộ: \(l-x\), mất \(\dfrac{l-x}{v_1}\)
  • Tổng thời gian của nhóm đó (tính từ lúc xuất phát) là:
\[\frac{x}{v_2} + \frac{l-x}{v_1}\]

Để nhóm đó kịp trong \(T\) thì cần:

\[\frac{x}{v_2} + \frac{l-x}{v_1} \le T\]

Từ đó suy ra một giới hạn trên cho \(x\) (vì đi xe lâu hơn đi bộ nếu kéo dài quá? Thực ra do \(v_2>v_1\) nên đi xe giúp giảm thời gian, nên với \(T\) cố định ta suy ra nhóm phải được xe chở ít nhất/đủ; biến đổi sẽ ra miền khả thi cho \(x\)).

Tuy nhiên, cách triển khai phổ biến và gọn hơn là mô phỏng theo từng chuyến bằng “khoảng cách gặp nhau” giữa xe (quay lại) và nhóm tiếp theo (đang đi bộ). Ta xét các chuyến theo thứ tự:

  • Ban đầu mọi người ở \(0\).
  • Sau khi xe chở nhóm 1 đi về phía trước một đoạn rồi quay lại, nhóm 2 đã đi bộ được một đoạn.
  • Xe phải quay lại đủ để “gặp” nhóm 2, đón họ, chở tiếp, v.v.

Điểm then chốt của kiểm tra: với thời gian \(T\), ta tính được xe có thể thực hiện bao nhiêu chuyến (tối đa \(m\)) sao cho sau chuyến cuối mọi người đều có thể tự đi bộ nốt để về kịp \(T\).

Công thức mô phỏng theo chuyến

Đặt:

  • \(m=\left\lceil \dfrac{n}{k}\right\rceil\) là số lượt chở.
  • Ta duy trì biến \(pos\): vị trí (tính theo mét) mà tại đó xe thả nhóm vừa chở xong (và nhóm này sẽ đi bộ nốt về đích).
  • Mỗi lần xe thả nhóm tại \(pos\), xe cần quay lại để gặp nhóm tiếp theo. Trong lúc xe chạy, nhóm tiếp theo vẫn đi bộ với \(v_1\).
  • Từ quan hệ chuyển động tương đối:
    • Khi xe quay lại với tốc độ \(v_2\) ngược chiều còn người đi bộ xuôi chiều \(v_1\), tốc độ “tiến lại gần nhau” là \(v_2+v_1\).
    • Khi xe chở nhóm xuôi chiều còn người đi bộ cũng xuôi chiều, tốc độ “bắt kịp” theo mô hình gặp điểm là \(v_2-v_1\).

Trong lời giải chuẩn, ta có thể tính trực tiếp thời gian cần thêm cho mỗi chuyến (trừ chuyến cuối không quay lại), từ đó kiểm tra tổng thời gian cần có \(\le T\).

Một cách trình bày kiểm tra thường dùng:

  • Giả sử ta muốn tất cả về trong \(T\).
  • Khi đó, ở thời điểm \(T\), nếu không có xe thì mỗi người đi được \(v_1T\); phần thiếu để tới khách sạn là \(l-v_1T\) (nếu dương).
  • Xe sẽ “bù” phần thiếu này bằng việc chở từng nhóm một đoạn sao cho tại thời điểm \(T\) họ kịp về.
  • Từ đó suy ra được mỗi chuyến xe phải đẩy “ranh giới” người đã được hỗ trợ tiến lên một mức, và ta kiểm tra sau \(m\) chuyến ranh giới có vượt \(l\) không.

Vì đề cho phép sai số \(10^{-6}\), cách triển khai sạch nhất là:

  1. Nhị phân đáp án \(T\).
  2. Hàm check(T) mô phỏng \(m\) chuyến theo công thức chuyển động tương đối (dùng số thực).
  3. Nếu sau \(m\) chuyến, điểm xa nhất mà nhóm cuối có thể đạt (và kịp đi bộ tới đích) \(\ge l\) thì check(T)=True.

Độ phức tạp

  • Mỗi lần check(T) chạy \(O(m)=O\left(\left\lceil \dfrac{n}{k}\right\rceil\right)\).
  • Nhị phân khoảng \(60\) vòng là đủ cho sai số \(10^{-6}\).
  • Tổng: \(O\left(60 \cdot \left\lceil \dfrac{n}{k}\right\rceil\right)\), với \(n\le 2\cdot 10^5\) chạy tốt.
  • Bộ nhớ: \(O(1)\).

Code tham khảo

C++
#include <bits/stdc++.h>
using namespace std;

/*
Lời giải chuẩn:

- Nhị phân thời gian T.
- check(T): mô phỏng m = ceil(n/k) chuyến.
Mô phỏng theo thời gian tích lũy:
    - time: thời gian đã trôi qua.
    - pos: vị trí xe (cũng là vị trí nhóm vừa được thả).
    - Nhóm tiếp theo luôn đi bộ từ 0, nên tại thời điểm time họ ở vị trí walk = v1*time.
    - Xe (ở pos) quay lại để gặp họ: cần t_back sao cho:
            pos - v2*t_back = walk + v1*t_back
      =>    t_back = (pos - walk) / (v1 + v2), nếu pos > walk, ngược lại t_back=0.
      Sau đó xe và nhóm gặp tại meet = walk + v1*t_back.
    - Xe chở nhóm từ meet tiến về phía trước đến pos_new trong t_go = (pos_new - meet)/v2.
      Ta chọn pos_new lớn nhất sao cho nếu thả ở đó thì họ kịp đi bộ nốt về đích trong T:
            time + t_back + t_go + (l - pos_new)/v1 <= T
      =>    pos_new <= l - v1*(T - (time + t_back + t_go))
      Giải trực tiếp cho pos_new:
            time2 = time + t_back
            Cần time2 + (pos_new - meet)/v2 + (l - pos_new)/v1 <= T
      Biến đổi:
            (pos_new - meet)/v2 - pos_new/v1 <= T - time2 - l/v1
            pos_new*(1/v2 - 1/v1) <= T - time2 - l/v1 + meet/v2
      Do (1/v2 - 1/v1) < 0, ta suy ra pos_new >= một ngưỡng.
      Trong tối ưu, ta luôn chọn pos_new = l (chở thẳng về) ở chuyến cuối,
      còn các chuyến trước chọn pos_new sao cho vừa đủ còn quay lại.
Thực tế, cách mô phỏng tối thiểu-time (không nhị phân) cũng được, nhưng nhị phân + check an toàn.

Lưu ý: Để ngắn gọn và chắc chắn, dưới đây dùng nhị phân + công thức đóng cho pos_new tối đa hợp lệ:
    From inequality:
        time2 + (pos_new - meet)/v2 + (l - pos_new)/v1 <= T
    Solve for pos_new:
        pos_new <= ( (T - time2) * v1 * v2 - l * v2 + meet * v1 ) / (v1 - v2)
    Vì v1 - v2 < 0 nên cần cẩn thận dấu; ta dùng long double và tính trực tiếp nghiệm,
    rồi clamp trong [meet, l].
*/

static inline bool check(long double T, long long n, long long l, long long v1, long long v2, long long k) {
    long long m = (n + k - 1) / k;
    long double time = 0.0L;
    long double pos = 0.0L; // vị trí xe sau khi thả nhóm hiện tại

    for (long long trip = 1; trip <= m; trip++) {
        // vị trí nhóm kế tiếp (đang đi bộ) tại thời điểm hiện tại
        long double walk = (long double)v1 * time;

        // quay lại để gặp (nếu xe đang ở phía trước)
        long double t_back = 0.0L;
        if (pos > walk) {
            t_back = (pos - walk) / ( (long double)v1 + (long double)v2 );
        }
        time += t_back;
        long double meet = walk + (long double)v1 * t_back; // vị trí gặp nhau

        // chuyến cuối: chở thẳng tới khách sạn
        if (trip == m) {
            time += ((long double)l - meet) / (long double)v2;
            return time <= T + 1e-12;
        }

        // Chọn pos_new lớn nhất sao cho nhóm này nếu bị thả ở pos_new thì kịp về trong T
        // time + (pos_new - meet)/v2 + (l - pos_new)/v1 <= T
        // Giải ra pos_new:
        // pos_new*(1/v2 - 1/v1) <= T - time - l/v1 + meet/v2
        // pos_new >= (T - time - l/v1 + meet/v2) / (1/v2 - 1/v1)
        // Do mẫu âm, để lấy pos_new lớn nhất vẫn thỏa, ta clamp pos_new = l (nhưng không được vì còn cần quay lại).
        // Trong mô phỏng check, ta chỉ cần một pos_new khả thi để tiếp tục; chọn pos_new sao cho đúng biên:
        long double rhs = (long double)T - time - (long double)l / (long double)v1 + meet / (long double)v2;
        long double denom = 1.0L / (long double)v2 - 1.0L / (long double)v1; // âm
        long double pos_new = rhs / denom; // sẽ là một giá trị trong [meet, l] nếu khả thi

        // Clamp để tránh sai số
        pos_new = min((long double)l, max(meet, pos_new));

        // cập nhật thời gian xe chở đến pos_new
        time += (pos_new - meet) / (long double)v2;
        pos = pos_new;

        // Nếu đã vượt quá T thì fail sớm
        if (time > T) return false;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, l, v1, v2, k;
    cin >> n >> l >> v1 >> v2 >> k;

    long double lo = 0.0L, hi = (long double)l / (long double)v1; // đi bộ toàn bộ là upper bound
    for (int it = 0; it < 80; it++) {
        long double mid = (lo + hi) / 2.0L;
        if (check(mid, n, l, v1, v2, k)) hi = mid;
        else lo = mid;
    }

    cout.setf(std::ios::fixed); cout << setprecision(10) << (double)hi << "\n";
    return 0;
}

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.