Editorial for ptit052: Bobs, Alice và cửa hàng thuốc

Hiểu bài toán

Bài toán mô phỏng quá trình Bob hút thuốc và đổi vỏ. Bob bắt đầu với $n$ bao thuốc. Mỗi ngày anh ta hút 1 bao và giữ lại vỏ. Khi có đủ $k$ vỏ (tức là sau mỗi $k$ ngày), anh ta có thể đổi $k$ vỏ lấy 1 bao thuốc mới. Câu hỏi là sau bao nhiêu ngày thì Bob không còn thuốc để hút. Đầu vào là $n$ và $k$, đầu ra là số ngày tối đa Bob có thể hút thuốc.

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

Cách Mô phỏng từng ngày (Simulation)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    int day = 0;
    while (n != 0) {
        n--; // Hút 1 bao
        day++; // Thời gian trôi qua 1 ngày
        if (day % k == 0) {
            n++; // Đổi được 1 bao mới nếu đến ngày đổi (sau mỗi k ngày)
        }
    }
    printf("%d", day);
    return 0;
}

• Time Complexity: O(day). Số ngày có thể lớn hơn $n$ một chút nhưng không vượt quá $n + n/(k-1)$ hoặc tương tự. Với $n=10^6$, độ phức tạp này chấp nhận được nhưng có thể chậm nếu $k$ nhỏ.
• Space Complexity: O(1)

Cách tiếp cận này mô phỏng chính xác quá trình từng ngày. Vòng lặp while chạy cho đến khi n (số thuốc còn lại) bằng 0. Mỗi lần lặp: giảm n đi 1 (hút thuốc), tăng day lên 1. Sau mỗi $k$ ngày (day % k == 0), tăng n lên 1 (đổi thuốc). Cách này dễ hiểu nhưng không hiệu quả về mặt thời gian nếu $n$ rất lớn.

Cách Tích lũy theo lô (Batch Processing)

#include<stdio.h>
#include<math.h>
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int tong=n;
    while(n>=k){
        int them=n/k;
        tong+=them;
        n=n%k+them;
    }
    printf("%d",tong);
}

• Time Complexity: O(log_k n). Vòng lặp chia $n$ cho $k$ mỗi lần, số lần lặp roughly logarit.
• Space Complexity: O(1)

Phương pháp này tối ưu hơn bằng cách xử lý nhiều ngày cùng lúc. Thay vì trừ từng ngày, ta trừ một lúc $k$ ngày (tương ứng 1 lần đổi). Trong biến tong ta lưu tổng số ngày đã qua. Biến n hiện tại lưu số thuốc Bob có bao gồm số thuốc đổi được. Vòng lặp while(n >= k) sẽ tính số thuốc đổi được (them = n/k), cộng vào tổng ngày, và cập nhật lại n là phần thuốc còn lại chưa đổi được (n % k) cộng với thuốc mới đổi được (them).

Cách Công thức toán học (Mathematical Formula)

#include <stdio.h>
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int days = 0;
    while (n) {
        if (n < k) {
            days += n;
            break;
        } else {
            n -= k;
            days += k;
        }
        n++;
    }
    printf("%d", days);
    return 0;
}

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

Đây là cách tiếp cận dạng 'tích lũy' khác. Nó chia nhỏ quá trình thành từng đợt 'hút $k$ ngày đổi 1 bao'. Cụ thể:

1. Trong khi còn thuốc:
   • Nếu thuốc còn ít hơn $k$: Hút hết số thuốc còn lại, cộng số ngày đó vào tổng rồi kết thúc.
   • Nếu thuốc đủ $k$: Hút $k$ bao (cộng $k$ ngày), sau đó số thuốc giảm đi $k$ nhưng được cộng thêm 1 bao mới (do đổi $k$ vỏ). Cách này về bản chất giống cách 2 nhưng cách viết code trực quan hơn một chút về mặt mô phỏng chu kỳ.

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

Bài học kinh nghiệm

• Vấn đề có thể được biến đổi thành bài toán tìm tổng số ngày bằng cách tính toán số lần đổi thuốc.
• Thay vì mô phỏng từng ngày, ta có thể nhóm các ngày lại thành các đợt (batch) tương ứng với mỗi lần đổi thuốc để tăng tốc độ xử lý.
• Số ngày tối đa không chỉ là $n$ ban đầu mà còn bao gồm số ngày được tạo ra từ việc đổi thuốc.

Lỗi thường gặp

• Quên cập nhật lại số thuốc sau khi đổi (sai logic vòng lặp).
• Làm tròn số lượng thuốc đổi được (phải dùng phép chia nguyên).
• Bị lặp vô hạn nếu logic điều kiện dừng sai (ví dụ: không giảm số thuốc đúng cách).