Hiểu bài toán

Một cửa hàng có M món hàng, mỗi món có giá bằng số thứ tự (1, 2, ..., M). Quy tắc đặc biệt: nếu mua một món hàng vào ngày hôm qua, thì phải mất 1 ngày nghỉ (không mua món đó) rồi mới có thể mua lại món đó. Câu hỏi: Anh có N đồng vàng, muốn mua quà liên tục nhiều ngày nhất có thể (mỗi ngày phải mua ít nhất 1 món, và tuân thủ quy tắc nhập hàng). Số ngày liên tục tối đa là bao nhiêu?

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

Cách Quy hoạch động / Mô phỏng (Brute Force)

// Chỉ mang tính tham khảo, không khả thi với N lớn
#include <iostream>
using namespace std;

int solve(int M, int N) {
    // Mô phỏng từng ngày, không khả thi vì N ~ 10^9
    return 0;
}

• Time Complexity: O(N) - Quá chậm, không khả thi
• Space Complexity: O(1)

Cách tiếp cận này sẽ mô phỏng từng ngày, thử các cách mua hàng. Tuy nhiên, do N có thể lên tới 10^9, cách này chắc chắn sẽ gây TLE (Time Limit Exceeded) và không thể sử dụng.

Cách Công thức toán học (Quy luật)

#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;
            continue;
        }
        // Tính số ngày có thể mua bằng công thức
        long long days = (N / 3) * 2;
        if (N % 3 != 0) days++;
        cout << days << endl;
    }
    return 0;
}

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

Khi M >= 2, ta luôn có thể xoay vòng 2 món hàng (ví dụ món 1 và món 2) để đạt hiệu quả chi phí thấp nhất.

• Mua 2 ngày liên tiếp: Món 1, Món 2. Chi phí: 1 + 2 = 3. Thời gian: 2 ngày.
• Quy luật: Cứ 3 đồng vàng, ta mua được 2 ngày. Công thức: days = (N / 3) * 2 + (N % 3 != 0 ? 1 : 0). Trường hợp đặc biệt: Nếu M = 1, ta chỉ có thể mua 1 ngày rồi phải nghỉ 1 ngày. Do đó chỉ mua được 1 ngày (dù N lớn bao nhiêu).

Cách Tìm kiếm nhị phân (Binary Search)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll cost(ll d) {
    // Tính chi phí tối thiểu để mua liên tục d ngày với M >= 2
    if (d % 2 == 0) return 3 * d / 2;
    return (3 * d - 1) / 2;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll M, N;
        cin >> M >> N;
        if (M == 1) {
            cout << 1 << endl;
            continue;
        }
        ll lo = 1, hi = N, ans = 1;
        while (lo <= hi) {
            ll mid = (lo + hi) / 2;
            // Kiểm tra xem có đủ tiền mua 'mid' ngày không
            if (cost(mid) <= N) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Ta tìm số ngày d tối đa sao cho chi phí <= N. Hàm chi phí cost(d) tính toán số tiền ít nhất cần thiết để mua liên tục d ngày.

• Với d chẵn: Ta xoay vòng 1-2... M-1-M. Chu kỳ 2 ngày tốn 3 đồng. Cần d/2 chu kỳ => 3*d/2.
• Với d lẻ: Tương tự d-1 ngày đầu tốn 3(d-1)/2, ngày cuối tốn 1 (hoặc 2 tùy M). Công thức gộp lại là (3d - 1)/2. Sử dụng Binary Search trên số ngày để tìm giá trị lớn nhất thỏa mãn.

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

Bài học kinh nghiệm

• Với M >= 2, luôn ưu tiên xoay vòng 2 món hàng có giá thấp nhất (1 và 2) để tiết kiệm chi phí nhất có thể.
• Mối quan hệ giữa số ngày và chi phí là tuyến tính: Cứ 3 đồng vàng mua được 2 ngày.
• Trường hợp M = 1 là ngoại lệ đặc biệt, chỉ trả về 1.

Lỗi thường gặp

• Quên xử lý trường hợp đặc biệt M = 1 (lúc này công thức chung sẽ sai, vì không thể xoay vòng).
• Sử dụng biến int导致 overflow khi tính toán với N lên tới 10^9. Phải dùng long long.
• Đặt sai giới hạn Binary Search (ví dụ hi = N thay vì N*2).