Hiểu bài toán

Bài toán yêu cầu tính thời gian tối thiểu (tính bằng phút, làm tròn lên số nguyên) để một con bò đọc xong một cuốn sách có N trang. Con bò thứ k có tốc độ đọc Sk trang/phút, nhưng chỉ có thể đọc liên tục tối đa Tk phút, sau đó phải nghỉ ít nhất R_k phút trước khi tiếp tục đọc. Quá trình đọc-nghỉ lặp lại cho đến khi đủ N trang được đọc.

Ví dụ: N=10, S=2, T=4, R=1. Trong 4 phút đầu, bò đọc được 8 trang. Còn 2 trang. Bò nghỉ 1 phút. Sau đó bò đọc tiếp. Để đọc 2 trang với tốc độ 2 trang/phút, cần 1 phút. Tổng thời gian: 4 (đọc) + 1 (nghỉ) + 1 (đọc) = 6 phút.

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

Cách Mô phỏng theo từng phút (Brute Force)

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    while(k--) {
        int s, t, r;
        cin >> s >> t >> r;
        int pages_read = 0;
        int time = 0;
        int read_time_left = t;
        bool is_reading = true;

        while(pages_read < n) {
            if(is_reading) {
                pages_read += s;
                time++;
                read_time_left--;
                if(read_time_left == 0) {
                    is_reading = false;
                    read_time_left = r; // Chuẩn bị cho thời gian nghỉ
                }
            } else {
                time++;
                read_time_left--;
                if(read_time_left == 0) {
                    is_reading = true;
                    read_time_left = t;
                }
            }
        }
        cout << time << endl;
    }
    return 0;
}

• Time Complexity: O(N * K)
• Space Complexity: O(1)

Cách tiếp cận này mô phỏng quá trình đọc từng phút một. Vòng lặp chính chạy cho đến khi số trang đọc được >= N. Trong mỗi phút:

1. Nếu đang đọc: cộng thêm S trang, giảm thời gian đọc còn lại. Hết thời gian đọc thì chuyển sang trạng thái nghỉ.
2. Nếu đang nghỉ: chỉ tăng thời gian. Hết thời gian nghỉ thì chuyển sang trạng thái đọc. Phương pháp này dễ hiểu nhưng chậm vì N có thể lên tới 10^5, và nếu tốc độ đọc S nhỏ, thời gian mô phỏng có thể rất lớn.

Cách Tính toán theo chu kỳ (Math)

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    while(k--) {
        int s, t, r;
        cin >> s >> t >> r;

        // Số trang đọc được trong 1 chu kỳ đầy đủ (đọc + nghỉ)
        int cycle_pages = s * t;

        // Số trang còn lại sau khi đọc hết các chu kỳ đầy đủ
        int remaining_pages = n % cycle_pages;

        // Số chu kỳ đầy đủ
        long long cycles = n / cycle_pages;

        // Thời gian cho các chu kỳ đầy đủ
        // Mỗi chu kỳ đầy đủ gồm T phút đọc + R phút nghỉ
        long long total_time = cycles * (long long)(t + r);

        // Xử lý phần trang còn lại
        if (remaining_pages == 0) {
            // Nếu đọc hết chu kỳ正好 đủ N trang, ta không cần nghỉ sau cùng
            // Nên trừ đi thời gian nghỉ R của chu kỳ cuối
            total_time -= r;
        } else {
            // Cần thêm thời gian để đọc nốt các trang còn lại
            // Thời gian đọc = ceil(remaining_pages / s)
            total_time += remaining_pages / s;
            if (remaining_pages % s != 0) {
                total_time += 1;
            }
        }

        cout << total_time << endl;
    }
    return 0;
}

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

Đây là phương pháp tối ưu, dựa trên nhận thức về cấu trúc chu kỳ lặp lại.

1. Chu kỳ cơ bản: Một chu kỳ bao gồm T phút đọc và R phút nghỉ.
2. Số trang mỗi chu kỳ: Trong mỗi chu kỳ đọc T phút, bò đọc được S * T trang.
3. Tính toán số chu kỳ: Chia N cho (S * T) để tìm số chu kỳ đọc đầy đủ cần thiết. Gọi số này là cycles.
4. Thời gian chu kỳ đầy đủ: cycles chu kỳ đầu tiên tốn cycles * (T + R) phút.
5. Xử lý trang dư: Nếu N chia hết cho S*T (trang dư = 0), bò đọc xong đúng lúc kết thúc một chu kỳ đọc. Tuy nhiên, quy tắc yêu cầu phải nghỉ R phút SAU KHI đọc xong T phút. Vì đọc xong là kết thúc luôn nên ta KHÔNG CẦN nghỉ thêm R phút đó nữa. Do đó trừ R. Nếu trang dư > 0, ta chỉ cần làm phần đầu của chu kỳ mới (thời gian đọc). Thời gian đọc phần dư là ceil(remaining / S).

Ví dụ: N=10, S=2, T=4, R=1.

• S*T = 8 trang/chu kỳ.
• cycles = 10 / 8 = 1. (Còn dư 2 trang).
• Thời gian chu kỳ đầy đủ: 1 * (4 + 1) = 5 phút.
• Trang dư: 2.
• Thời gian đọc dư: ceil(2/2) = 1 phút.
• Tổng: 5 + 1 = 6 phút.

Ví dụ N=16, S=2, T=4, R=1.

• S*T = 8.
• cycles = 2. (Dư 0).
• Thời gian chu kỳ: 2 * (4 + 1) = 10.
• Trang dư 0 => Trừ R: 10 - 1 = 9.
• Kiểm tra: 4 phút đọc (8 trang) -> 1 phút nghỉ -> 4 phút đọc (8 trang). Hết 16 trang. Dừng. Tổng 9 phút. Đúng.

Cách Giải thích Logic Nén (Cùng bản chất Math)

// Code này tương tự Approach 2, nhưng giải thích theo biến tổng quan
// Xem T là tốc độ trang/phút (Rate) thay vì Speed
#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    while(k--) {
        int s, t, r;
        cin >> s >> t >> r;

        // 1. Tính thời gian đọc liên tục không nghỉ
        // Nếu đọc liên tục, cần ceil(n/s) phút.
        // Nhưng bị giới hạn bởi T.

        // 2. Gọi P là năng suất mỗi chu kỳ: s * t trang.
        // Gọi Q là độ dài chu kỳ: t + r phut.

        // 3. Số chu kỳ đầy đủ: n / (s*t)
        long long p = n / (s * t);
        // Phần trang còn lại
        int x = n % (s * t);

        // 4. Tính tổng thời gian
        long long ans = p * (t + r);

        if (x > 0) {
            // Cần thêm thời gian đọc phần còn lại
            ans += x / s;
            if (x % s != 0) ans++;
        } else {
            // Nếu không có trang dư, ta đã đếm thừa thời gian nghỉ R của chu kỳ cuối
            ans -= r;
        }

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

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

Đây là cách trình bày chi tiết hơn của Approach 2, làm rõ các biến số.

• Biến p: Số lượng chu kỳ đọc-trọn-vẹn (đủ T phút).
• Biến x: Số trang còn lại không đủ tạo thành một phiên đọc T phút.
• Công thức: Tổng thời gian = (Thời gian các chu kỳ đọc-trọn-vẹn) + (Thời gian đọc phần còn lại).
• Nếu x == 0: Chu kỳ cuối cùng đọc xong T phút là kết thúc. Ta không cần nghỉ R phút sau đó. Do đó trừ R.
• Nếu x > 0: Ta cần thêm thời gian để đọc xong x trang. Thời gian này được tính trọn vẹn (không bị gián đoạn giữa chừng do hết giờ T).

Lưu ý về số nguyên: Câu hỏi yêu cầu 'làm tròn kết quả lên số nguyên dương nhỏ nhất'. Trong lập trình thi đấu, khi chia số nguyên, ceil(a/b) thường được tính là (a + b - 1) / b hoặc a/b + (a%b > 0). Ở đây x/s là chia số nguyên, nếu x%s > 0 thì ta cộng thêm 1.

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

Bài học kinh nghiệm

• Bài toán có tính chất chu kỳ lặp lại (Reading block + Resting block).
• Tốc độ đọc là không đổi trong giai đoạn hoạt động, nên ta có thể tính toán lượng trang đọc được bằng phép nhân.
• Điều kiện dừng quan trọng: Nếu đọc xong đúng lúc kết thúc một phiên đọc (đạt T phút), ta không cần thực hiện thời gian nghỉ R.
• Bài toán có thể giải quyết bằng O(1) cho mỗi con bò thay vì mô phỏng.

Lỗi thường gặp

• Quên trừ đi thời gian nghỉ R khi đọc xong đúng chu kỳ (trang dư = 0). Nếu không trừ, đáp án sẽ bị dư R.
• Sai lệch biến N và K: Input mẫu cho thấy thứ tự là N K, nhưng một số code (Solution 3) lại đọc là K N, đây là lỗi logic nhập input.
• Làm tròn sai: Cần đảm bảo tính thời gian đọc phần dư đúng theo quy tắc 'lớn hơn hoặc bằng'. Ví dụ: 1 trang, tốc độ 2 trang/phút cần 1 phút.
• Tràn số: N lên tới 10^5, nhưng tích S*T có thể nhỏ. Nếu dùng biến int cho kết quả trung gian có thể tràn số nếu tính tích S*T*N trước, nên chia nhỏ phép tính hoặc dùng long long.
• Xử lý零头 sai: Solution 3 (while (S < res)) có vẻ như đang mô phỏng và cộng dồn S, nhưng logic res = res - S và S = 0 có thể sai logic nếu S (lượng đọc trong 1 chu kỳ) lớn hơn res (số trang còn lại) ngay từ đầu.