Bài A – Quản Lý Đơn Hàng Sản Xuất

Một nhà máy có khả năng sản xuất k đơn vị sản phẩm mỗi ngày. Có n đơn hàng, mỗi đơn hàng i yêu cầu giao b_i sản phẩm vào ngày a_i. Cần xác định xem có thể đáp ứng toàn bộ các đơn hàng hay không.

Giải pháp: Sắp xếp các đơn hàng theo thời điểm giao tăng dần. Duyệt tuần tự, tích lũy số lượng sản phẩm có thể sản xuất từ thời điểm trước đến thời điểm hiện tại (tức là k × (a_i − a_{i−1})), rồi trừ đi số lượng cần giao. Nếu tại bất kỳ bước nào tổng tích lũy âm, nghĩa là không đủ hàng — kết luận "No". Ngược lại, sau khi xử lý hết tất cả đơn hàng mà không vi phạm ràng buộc, kết luận "Yes".

Dưới đây là phiên bản đã cải tiến của mã nguồn với cấu trúc rõ ràng hơn, tên biến mang tính mô tả và loại bỏ các macro không cần thiết:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Order {
    long long deadline;
    long long quantity;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long n, k;
        cin >> n >> k;
        vector<Order> orders(n);
        for (auto& o : orders) {
            cin >> o.deadline >> o.quantity;
        }
        sort(orders.begin(), orders.end(), [](const Order& x, const Order& y) {
            return x.deadline < y.deadline;
        });

        long long available = 0;
        long long prev_day = 0;
        bool feasible = true;

        for (const auto& ord : orders) {
            available += k * (ord.deadline - prev_day);
            prev_day = ord.deadline;
            if (available < ord.quantity) {
                feasible = false;
                break;
            }
            available -= ord.quantity;
        }

        cout << (feasible ? "Yes" : "No") << '\n';
    }
    return 0;
}

Bài D – Tối Ưu Hóa Tốc Độ Đội Nhóm

Có n người, mỗi người có tốc độ v_i và trọng lượng w_i. Một người có thể cõng một người khác nếu trọng lượng người được cõng không vượt quá trọng lượng người cõng. Khi cõng, tốc độ chung của cặp là min(v_i, v_i − (w_i − w_j)), với điều kiện w_j ≤ w_i; nếu biểu thức bên trong âm hoặc bằng 0 thì không thể cõng. Mục tiêu là chọn cách ghép sao cho tốc độ tối thiểu của tất cả các cá nhân (sau khi ghép hoặc đứng riêng) là lớn nhất có thể.

Phương pháp: Sử dụng tìm kiếm nhị phân trên giá trị tốc độ mục tiêu x. Với mỗi x, kiểm tra xem có thể bố trí sao cho mọi người đều đạt ít nhất x. Người có v_i ≥ x có thể đóng vai trò người cõng, và khả năng cõng tối đa của họ phụ thuộc vào v_i + w_i − x — đây là giới hạn trên về trọng lượng người bị cõng. Những người có v_i < x phải được cõng, và ta ưu tiên ghép người có trọng lượng cao nhất với người cõng có khả năng chịu tải cao nhất. Nếu số người cần được cõng vượt quá số người có thể cõng, hoặc không thể ghép phù hợp, thì x không khả thi.

Mã nguồn tái cấu trúc với logic minh bạch và sử dụng std::vector thay vì queue thủ công:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

struct Person {
    long long speed, weight;
};

bool canAchieve(const vector<Person>& people, long long target) {
    vector<long long> carriers;
    vector<long long> riders;

    for (const auto& p : people) {
        if (p.speed >= target) {
            carriers.push_back(p.speed + p.weight - target);
        } else {
            riders.push_back(p.weight);
        }
    }

    sort(carriers.rbegin(), carriers.rend());
    sort(riders.rbegin(), riders.rend());

    if (riders.size() > carriers.size()) return false;

    for (size_t i = 0; i < riders.size(); ++i) {
        if (carriers[i] < riders[i]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<Person> team(n);
        long long low = LLONG_MAX, high = 0;

        for (auto& p : team) {
            cin >> p.speed >> p.weight;
            low = min(low, p.speed);
            high = max(high, p.speed);
        }

        while (low < high) {
            long long mid = low + (high - low + 1) / 2;
            if (canAchieve(team, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        cout << low << '\n';
    }
    return 0;
}

Bài E – Chuyển Đổi Số Nguyên Về Bội Của m

Cho số nguyên dương n, cần biến đổi nó thành một bội số của m thông qua hai phép toán:

• Phép nhân mở rộng: Thay n bằng n × k + x, với 1 ≤ x ≤ k, chi phí là a.
• Phép chia nguyên: Thay n bằng ⌊n / k⌋, chi phí là b.

Mục tiêu là tìm chi phí nhỏ nhất để đạt được trạng thái mong muốn.

Quan sát then chốt: Vì phép chia làm giảm giá trị và phép nhân mở rộng luôn cộng thêm một phần dư nhỏ (< k), nên ta chỉ cần xét chuỗi các phép chia liên tiếp cho đến khi n = 0 (vì 0 là bội của mọi m). Tại mỗi bước trước khi chia, ta có thể thực hiện một hoặc nhiều lần phép nhân mở rộng để đưa n về gần nhất với một bội số của m. Việc này được thực hiện bằng cách mô phỏng phép nhân modulo m và cập nhật chi phí tích lũy.

Mã nguồn được viết lại hoàn toàn với vòng lặp rõ ràng, tránh đệ quy và xử lý trường hợp đặc biệt k == 1 ngay từ đầu:

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        long long n, k, m, a, b;
        cin >> n >> k >> m >> a >> b;

        if (n % m == 0) {
            cout << "0\n";
            continue;
        }
        if (k == 1) {
            cout << "-1\n";
            continue;
        }

        long long min_cost = LLONG_MAX;
        long long accumulated_cost = 0;

        while (true) {
            long long remainder = n % m;
            long long cost_to_multiple = 0;
            long long current_remainder = remainder;
            long long multiplier = 1;

            // Tìm số lần nhân tối thiểu để đạt bội số của m
            while (current_remainder != 0) {
                cost_to_multiple += a;
                current_remainder = (current_remainder * k) % m;
                multiplier *= k;
                if (multiplier > m) break; // Tránh tràn và lặp vô hạn
            }

            min_cost = min(min_cost, accumulated_cost + cost_to_multiple);

            if (n == 0) break;

            n /= k;
            accumulated_cost += b;
        }

        cout << min_cost << '\n';
    }
    return 0;
}

Bài I – Phân Tích Mặt Xúc Xắc Màu

Mỗi xúc xắc có 6 mặt, trong đó mặt số 1 và 4 là màu đỏ; các mặt còn lại (2, 3, 5, 6) là đen. Cho ba xúc xắc, ký hiệu tổng số chấm trên các mặt đỏ là a, tổng số chấm trên các mặt đen là b. Kiểm tra xem tồn tại cách lăn ba xúc xắc sao cho thỏa mãn đồng thời hai tổng này.

Phương pháp: Liệt kê tất cả khả năng số mặt đỏ có thể xuất hiện (0 đến 3), tương ứng với số mặt đen là (3 đến 0). Với mỗi số mặt đỏ r, tổng chấm đỏ a phải là tổng của r giá trị lấy từ tập {1, 4}, và tổng chấm đen b phải là tổng của 3−r giá trị lấy từ tập {2, 3, 5, 6}. Vì không gian nghiệm nhỏ, ta dùng brute-force có kiểm soát: sinh tất cả tổ hợp có thể cho từng r, so sánh với a và b.

Mã nguồn được tối ưu hóa để tránh lặp thừa và sử dụng tập hợp set để kiểm tra nhanh:

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    cin >> a >> b;

    set<pair<int, int>> valid_pairs;

    // r = số mặt đỏ (0..3)
    vector<int> red_faces = {1, 4};
    vector<int> black_faces = {2, 3, 5, 6};

    for (int r = 0; r <= 3; ++r) {
        vector<int> red_choices;
        for (int i = 0; i < (1 << red_faces.size()); ++i) {
            if (__builtin_popcount(i) == r) {
                int sum = 0;
                for (int j = 0; j < (int)red_faces.size(); ++j) {
                    if (i & (1 << j)) sum += red_faces[j];
                }
                red_choices.push_back(sum);
            }
        }

        vector<int> black_choices;
        for (int i = 0; i < (1 << black_faces.size()); ++i) {
            if (__builtin_popcount(i) == 3 - r) {
                int sum = 0;
                for (int j = 0; j < (int)black_faces.size(); ++j) {
                    if (i & (1 << j)) sum += black_faces[j];
                }
                black_choices.push_back(sum);
            }
        }

        for (int ra : red_choices) {
            for (int ba : black_choices) {
                valid_pairs.insert({ra, ba});
            }
        }
    }

    cout << (valid_pairs.count({a, b}) ? "Yes" : "No") << '\n';
    return 0;
}