Hiểu bài toán

Cho ba số nguyên dương n, k, p ≤ 10^9. Giá mua lẻ mỗi chiếc bút chì là p. Cứ mỗi k chiếc bút chì mua, bạn được tặng thêm 1 chiếc. Cần tìm số tiền tối thiểu để mang về ít nhất n chiếc bút chì.

Ví dụ: n=36, k=5, p=5. Mua 30 chiếc được tặng 6 chiếc (tổng 36). Số tiền = 30 * 5 = 150.

Quy luật: Nếu mua x bút, bạn nhận được x + floor(x/k) bút. Cần tìm x nhỏ nhất sao cho x + floor(x/k) ≥ n.

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

Cách Công thức trực tiếp

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

int main() {
    long long n, k, p;
    cin >> n >> k >> p;
    // Số tiền = (số lượng mua) * p
    // Số lượng mua = n - floor(n / (k+1))
    cout << (n - n / (k + 1)) * p;
    return 0;
}

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

Cách tiếp cận này dựa trên việc phân tích toán học:

1. Gọi x là số lượng bút mua, t là số lượng bút được tặng.
2. Tổng số bút nhận được: x + floor(x/k) ≥ n
3. Chuyển đổi bài toán: Tìm x tối thiểu thỏa mãn x ≥ n - floor(x/k)

Quan sát thấy số lần tặng phụ thuộc vào số lượng mua, nhưng có thể tính trực tiếp:

• Trong n bút cần thiết, có một số lượng được nhận miễn phí.
• Tỷ lệ bút miễn phí so với bút mua là 1:k, tức là 1/(k+1) tổng số bút nhận được.
• Do đó, số lượng bút cần mua = n - floor(n/(k+1))

Ví dụ: n=36, k=5

• floor(36/6) = 6 bút được tặng
• Cần mua: 36 - 6 = 30 bút
• Số tiền: 30 * p

Công thức: (n - n/(k+1)) * p

Đảm bảo dùng số nguyên 64-bit (long long) vì n, k, p có thể lên đến 10^9.

Cách Công thức nhân tử

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

int main() {
    long long n, k, p;
    cin >> n >> k >> p;
    // Số tiền = ((n / (k+1) * k) + (n % (k+1))) * p
    cout << p * ((n / (k + 1) * k) + (n % (k + 1)));
    return 0;
}

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

Cách tiếp cận khác nhưng cùng bản chất:

Phân chia n thành 2 phần:

1. Phần chia hết cho (k+1): n/(k+1) * k bút cần mua
2. Phần dư: n%(k+1) bút cần mua (không đủ để nhận thêm)

Ví dụ: n=36, k=5

• 36 = 5*6 + 6
• Phần chia hết: 6 nhóm → mua 6*5 = 30 bút
• Phần dư: 6 → mua 6 bút
• Tổng mua: 30 + 6 = 36
• Số tiền: 36 * p = 180? Sai!

Chú ý: Phần dư không phải lúc nào cũng mua đủ. Thực tế:

• Nếu phần dư > 0, ta mua phần dư đó
• Nhưng cách tính này chỉ đúng khi phần dư được xem như "mua không được tặng"

Đúng hơn: n = (k+1)*a + b, với 0 ≤ b < k+1

• Mua a*k + b bút
• Nhận a*bút tặng
• Tổng: ak + b + a = a(k+1) + b = n

Vậy: Số tiền = (ak + b)p = ((n/(k+1))k + n%(k+1))p

Cách Tìm kiếm nhị phân

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

long long calculateTotal(long long x, long long k) {
    return x + x / k;
}

int main() {
    long long n, k, p;
    cin >> n >> k >> p;

    long long left = 1, right = n, answer = n;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (calculateTotal(mid, k) >= n) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << answer * p;
    return 0;
}

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

Sử dụng tìm kiếm nhị phân để tìm số lượng bút cần mua:

1. Xác định miền tìm kiếm: từ 1 đến n (vì mua n bút chắc chắn đủ)
2. Hàm kiểm tra: x + floor(x/k) >= n
3. Tìm giá trị nhỏ nhất thỏa mãn

Ưu điểm:

• Dễ hiểu, trực quan
• Không cần suy luận công thức phức tạp
• Luôn đúng với mọi trường hợp

Nhược điểm:

• Phức tạp hơn O(1)
• Có thể tràn số nếu không dùng đúng kiểu dữ liệu

Tuy nhiên, với n ≤ 10^9, O(log n) ≈ 30 bước là hoàn toàn chấp nhận được.

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

Bài học kinh nghiệm

• Mối quan hệ giữa số lượng mua và nhận được: x + floor(x/k) ≥ n
• Công thức tối ưu: Số tiền = (n - floor(n/(k+1))) * p
• Bài toán có thể biến đổi về công thức toán học không cần tìm kiếm

Lỗi thường gặp

• Tràn số: Phải dùng long long (64-bit) vì 10^9 * 10^9 = 10^18 > 2^31
• Lỗi logic: Đếm số lần tặng dựa trên số lượng mua thay vì tổng số nhận được
• Quên xử lý trường hợp đặc biệt: k=0 (không được tặng) hay k rất lớn