Hiểu bài toán

Anh có N đồng vàng và muốn mua quà tại cửa hàng có M món hàng (giá từ '。。 (。n.。。

nnnn

n.

n n

。

M n

...
。。.+. cửa shop M. .. phải. và shop... trong� '..

cửa...

giorni。]\n.. m m An。 T2 m

, M và '? là. An An và và so

M store\k ( s➔ mua, Anh có thể mua vào các ngày 1, 2, 4, 5, 7, 8, ... (mua 2 ngày, nghỉ 1 ngày). Ví dụ: M=3, N=3, Anh có thể mua món 1 ngày 1, món 2 ngày 2, sau đó phải nghỉ ngày 3 (vì món 1,2 vẫn chưa về lại), nhưng sang ngày 4 có thể mua món 3 hoặc mua lại món 1. Tuy nhiên, để tối ưu số ngày liên tiếp, Anh cần chọn chiến lược mua đồ sao cho số ngày liên tiếp là lớn nhất. Mục tiêu: Tìm số ngày liên tiếp dài nhất mà Anh có thể mua quà liên tục với tổng chi phí ≤ N.

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

Cách Phân tích quy luật chu kỳ (Công thức trực tiếp)

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long M, N;
        cin >> M >> N;
        if (M == 1) {
            cout << 1 << endl;
        } else {
            long long full_pairs = N / 3;
            long long days = full_pairs * 2;
            if (N % 3 != 0) {
                days++;
            }
            cout << days << endl;
        }
    }
    return 0;
}

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

Đối với M ≥ 2, Anh có thể mua tối đa 2 ngày liên tiếp trong một chu kỳ 3 ngày (ví dụ: mua ngày 1,2; nghỉ ngày 3). Mô hình này lặp lại: chi phí 3 đồng cho 2 ngày mua.

• Nếu N chia hết cho 3: Số cặp full là N/3, mỗi cặp cho 2 ngày => tổng ngày = (N/3)*2.
• Nếu N không chia hết cho 3: Vẫn có (N/3) cặp full cho (N/3)*2 ngày, và phần dư (N%3) >= 1. Với 1 đồng dư, ta có thể mua thêm 1 ngày (ngày đầu tiên của chu kỳ mới).
• Với M=1: Chỉ có 1 món hàng, sau khi bán xong phải nghỉ 1 ngày. Chu kỳ 2 ngày (1 bán, 1 nghỉ). N ≥ M = 1. Nếu N=1, mua được 1 ngày. Nếu N>1, vẫn chỉ mua được 1 ngày rồi phải nghỉ, nhưng để liên tiếp, ta chỉ được mua 1 ngày đầu rồi phải nghỉ để hàng về lại. Tuy nhiên, theo mẫu thử và logic tối ưu, với M=1, đáp án luôn là 1 vì không thể mua 2 ngày liên tiếp (cần 2 ngày cho 1 chu kỳ nhưng chỉ có 1 món).

Cách Mô phỏng chu kỳ với Logic Lập trình

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        long long M, N;
        cin >> M >> N;
        if (M == 1) {
            cout << 1 << '\n';
        } else {
            long long days = 0;
            long long h = N / 3;
            long long l = N % 3;
            days = h * 2;
            if (l != 0) days++;
            cout << days << '\n';
        }
    }
    return 0;
}

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

Cách tiếp cận này mô phỏng lại công thức ở trên dưới dạng mã nguồn. Nó tính số lượng 'cặp' đầy đủ (3 đồng) và số ngày tương ứng. Biến l (phần dư) kiểm tra xem có đủ 1 hoặc 2 đồng còn sót lại để mua thêm một ngày đầu tiên của chu kỳ tiếp theo hay không. Logic này hoàn toàn dựa trên việc nhận ra rằng với M ≥ 2, ta có thể mua tối đa 2 ngày và phải nghỉ 1 ngày (tỷ lệ 2:1).

Cách Tối ưu hóa M=1 và Chu kỳ M>=2

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        long long n, m;
        cin >> m >> n;
        if (m == 1) {
            cout << 1 << endl;
        } else {
            // Vòng lặp 3 ngày chi phí 3, được 2 ngày mua
            // N / 3 là số vòng lặp full
            // N % 3 là phần còn lại, nếu > 0 thêm 1 ngày
            long long ans = (n / 3) * 2;
            if (n % 3) ans++;
            cout << ans << endl;
        }
    }
    return 0;
}

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

Đây là phiên bản tổng quát nhất của phương pháp toán học. Nó xử lý riêng biệt trường hợp M=1 (vì giới hạn về số lượng hàng hóa vật lý) và M≥2 (vì lúc này số lượng hàng đủ để tạo chu kỳ 2 ngày mua - 1 ngày nghỉ). Công thức (N / 3) * 2 + (N % 3) > 0 ? 1 : 0 là tối ưu nhất.

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

Bài học kinh nghiệm

• Vấn đề cốt lõi là tìm chu kỳ chi phí tối ưu cho việc mua sắm liên tục. Với M ≥ 2, chu kỳ tối ưu là 'mua 2 ngày, nghỉ 1 ngày' (chi phí 3 cho 2 ngày).
• Trường hợp đặc biệt M=1: Vì chỉ có 1 món hàng, Anh không thể mua liên tiếp 2 ngày. Sau khi mua ngày 1, phải đợi ngày 2 để hàng về, nhưng chỉ có thể mua lại vào ngày 3. Do đó, số ngày liên tiếp tối đa là 1 (mua ngày 1, hoặc chọn 1 ngày bất kỳ trong tương lai, nhưng để liên tiếp thì chỉ được 1 ngày).

Lỗi thường gặp

• Quên xử lý trường hợp M=1 riêng: Nếu áp dụng công thức chung cho M=1, ta sẽ得到 (N/3)*2 + ... nhưng thực tế M=1 chỉ mua được 1 ngày.
• Sử dụng biến sai kiểu (int) cho N và M vì giới hạn lên đến 10^9, cần dùng long long.
• Sai logic về việc nghỉ ngơi: Nghĩ rằng có thể mua liên tục nếu có nhiều tiền mà quên mất quy tắc 'hết hàng phải đợi 1 ngày'.