Editorial for maze: Thoát khỏi mê cung

Hiểu bài toán

Mê cung gồm n+1 phòng nối tiếp nhau từ 1 đến n+1. Long bắt đầu ở phòng 1 tại thời điểm 0. Giữa phòng i và i+1 có một cánh cửa mở ra theo chu kỳ ai giây (mở tại thời điểm 0, ai, 2a_i, ...). Long muốn đến phòng n+1 càng sớm càng tốt. Khi đến một cánh cửa, nếu nó đang đóng, Long phải đợi cho đến khi nó mở ra. Di chuyển giữa các phòng không tốn thời gian. Hãy tìm thời điểm sớm nhất Long có thể thoát khỏi mê cung.

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

Cách Mô phỏng theo chu kỳ (Simulation)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long t = 0;
    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;
        // Nếu t chia hết cho a, cửa đang mở, đi qua luôn
        // Nếu không, phải đợi đến mốc a tiếp theo
        if (t % a != 0) {
            t = (t / a + 1) * a;
        }
    }
    cout << t << endl;
    return 0;
}

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

Giả lập quá trình di chuyển. Duy trì biến t là thời điểm hiện tại. Với mỗi cửa hàng a_i:

• Nếu t là bội số của a_i (tức t % a_i == 0), cửa đang mở, Long đi qua ngay lập tức.
• Nếu không, Long phải đợi đến mốc mở cửa tiếp theo lớn hơn hoặc bằng t. Mốc này là (t / a_i + 1) * a_i. Cách này mô phỏng chính xác quá trình chờ đợi của Long.

Cách Tối ưu hóa bằng công thức (Formula Optimization)

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

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

    long long n;
    cin >> n;
    vector<long long> a(n);
    for(long long &x : a) cin >> x;

    long long t = 0;
    for(long long x : a) {
        if (t == 0) t = x; // Cửa đầu tiên
        else {
            // Tính số nguyên k nhỏ nhất sao cho k*x >= t
            long long k = (t + x - 1) / x;
            t = k * x;
        }
    }
    cout << t;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n) (do lưu mảng, có thể tối ưu O(1))

Cách tiếp cận này thực chất là mô phỏng nhưng dùng công thức toán học để tính thời điểm mở cửa kế tiếp một cách gọn gàng.

• Với mỗi chu kỳ x, ta cần tìm số nguyên k nhỏ nhất sao cho k*x >= t.
• Công thức để tìm k là ceil(t / x) = (t + x - 1) / x.
• Sau đó cập nhật t = k * x. Logic này tương đương hoàn toàn với cách mô phỏng nhưng có thể ngắn gọn hơn.

Cách Cách tiếp cận chia hết trực tiếp (Direct Division Check)

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    long long result = A[0];
    for (int i = 1; i < N; ++i)
    {
        int time_wait = result % A[i]; 
        if (time_wait == 0) continue;
        else result += A[i] - time_wait;
    }
    cout << result;
    return 0;
}

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

Cách này xử lý riêng cửa đầu tiên và các cửa sau.

• result được khởi tạo bằng thời gian qua cửa đầu tiên (A[0]).
• Với các cửa tiếp theo, ta tính số dư result % A[i]. Nếu bằng 0 thì không cần chờ.
• Nếu không bằng 0, ta cần cộng thêm A[i] - (result % A[i]) để result trở thành bội số của A[i]. Ví dụ: result=4, A[i]=3. 4 % 3 = 1. Cần thêm 2 giây nữa (3-1) để lên 6. Lưu ý: Trong C++ với số âm dấu % có thể âm, nhưng ở đây result và A[i] đều dương nên không sao.

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

Bài học kinh nghiệm

• Bài toán có tính quy hoạch động đơn giản: thời điểm đến phòng i phụ thuộc hoàn toàn vào thời điểm đến phòng i-1 và chu kỳ mở cửa của cửa i.
• Không cần quan tâm đến việc Long có thể làm gì trong lúc chờ (vì không có việc khác để làm), chỉ cần tính thời điểm sớm nhất có thể đi qua.
• Thời điểm qua cửa là bội số của a_i lớn nhất hoặc bằng thời điểm đến cửa đó.

Lỗi thường gặp

• Tràn số (Integer Overflow): a_i lên tới 10^9 và có thể có tới 10^5 cửa. Nếu Long phải đợi nhiều lần, tổng thời gian có thể lên tới 10^14. Phải dùng kiểu dữ liệu 64-bit (long long trong C++).
• Sai công thức làm tròn số nguyên: Tính ceil(t / x) cần cẩn thận với số lớn. Công thức (t + x - 1) / x an toàn hơn ceil((double)t/x) (tránh sai số dấu phẩy động) và (t/x + (t%x!=0))*x.
• Xử lý sai trường hợp chia hết: if (t % a == 0) là điều kiện để đi qua không cần chờ, ngược lại phải chờ.