T1: P14056 [MX-X21-T1] [IAMOI R5] Hệ Thống Nghỉ Ngơi 7 Ngày

Bạn có ba loại ngày:

• Tập Luyện: Mức độ mệt mỏi +1.
• Nghỉ Ngơi: Mức độ mệt mỏi không thay đổi.
• Đuối Sức: Mức độ mệt mỏi -1.

Mức độ mệt mỏi ban đầu là 0, tổng cộng có a + b + c ngày, trong đó cần phải có chính xác a ngày tập luyện, b ngày nghỉ ngơi, và c ngày đuối sức. Bạn có thể sắp xếp thứ tự tùy ý, tìm số ngày mà mức độ mệt mỏi bằng 0.

Ý tưởng

Thuật toán sử dụng: tham lam.

Dựa theo phương pháp tham lam, chúng ta nghỉ ngơi b ngày trước (đóng góp cho kết quả là b). Sau đó luân phiên giữa các ngày tập luyện và đuối sức (đóng góp cho kết quả là min(a, c)). Kết quả cuối cùng là b + min(a, c).

#include <iostream>
using namespace std;

int main() {
    int x, y, z;
    cin >> x >> y >> z;
    cout << y + min(x, z) << "\n";
    return 0;
}

T2: P14057 [MX-X21-T2] [IAMOI R5] Bóng Nước Không Khí

Có n cái ly, đánh số từ 1 đến n, mỗi cái có dung tích m. Hiện tại, lượng nước trong ly thứ i là ai.

Bạn có thể thực hiện một số lần thao tác, mỗi lần chọn hai ly khác nhau i và j, đổ tất cả nước từ i vào j. Nếu sau khi đổ, lượng nước trong j vượt quá m thì lượng nước sẽ bị tràn chỉ còn lại m.

Sau khi hoàn thành các thao tác, bạn cần đảm bảo lượng nước trong từng ly không giảm và tổng lượng nước lớn nhất có thể. Tìm giá trị tối đa này.

Ý tưởng

Thuật toán sử dụng: tham lam.

Nếu các ly đã được sắp xếp tăng dần, câu trả lời rõ ràng là tổng lượng nước trong tất cả các ly. Nếu không, ít nhất cần hợp nhất một lần. Khi hợp nhất, tạo ra một ly trống để làm trung gian giúp các ly còn lại được sắp xếp tăng dần mà không lãng phí nước.

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long m;
        cin >> n >> m;
        long long sum = 0;
        long long arr[n+1];
        bool sorted = true;
        for(int i=1; i<=n; ++i){
            cin >> arr[i];
            sum += arr[i];
            if(i > 1 && arr[i] < arr[i-1]) sorted = false;
        }
        if(sorted){
            cout << sum << "\n";
        } else {
            sort(arr+1, arr+n+1);
            cout << sum - arr[1] - arr[2] + min((long long)m, arr[1]+arr[2]) << "\n";
        }
    }
    return 0;
}

T3: P14058 [MX-X21-T3] [IAMOI R5] Buổi Biểu Diễn Của Hai Người

Cho một vòng tròn gồm n số nguyên dương a1, a2, ..., an. Phân chia vòng tròn thành nhiều đoạn sao cho cực đại nội bộ của mỗi đoạn nhỏ hơn hoặc bằng m. Tìm số đoạn nhỏ nhất.

Ý tưởng

Thuật toán sử dụng: tham lam.

Xét trường hợp là một chuỗi, dùng thuật toán tham lam để tìm số lần phân chia ít nhất. Nếu là vòng tròn, thử phá vòng tròn thành chuỗi và áp dụng thuật toán tham lam. Nếu toàn bộ vòng tròn có cực đại ≤ m, câu trả lời là 1. Trường hợp khác, chia đôi kết quả của thuật toán tham lam.

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

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

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        int arr[2*n+1], maxv = 0, minv = 1e9, ans = 1;
        for(int i=1; i<=n; ++i){
            cin >> arr[i];
            arr[i+n] = arr[i];
        }

        for(int i=1; i<=2*n; ++i){
            maxv = max(maxv, arr[i]);
            minv = min(minv, arr[i]);
            if(maxv - minv > m){
                ans++;
                maxv = minv = arr[i];
            }
        }
        cout << (ans/2 == 0 ? 1 : ans/2) << "\n";
    }
    return 0;
}

T4: P14059 [MX-X21-T4] [IAMOI R5] Bảo Vệ Một Trái Tim

Một vòng tròn chứa các quân cờ đen trắng xen kẽ. Hai người chơi xoay vòng nhau xóa một đoạn liên tiếp các quân cùng màu (Robin chỉ xóa đen, Sunday chỉ xóa trắng). Nếu chỉ còn một màu duy nhất, trò chơi kết thúc: nếu toàn trắng Robin thắng, nếu toàn đen Sunday thắng.

Ý tưởng

Thuật toán sử dụng: phân loại thảo luận.

Trước tiên xét các trường hợp đơn giản: nếu chỉ có một màu duy nhất hoặc chỉ có hai đoạn màu, dễ dàng đưa ra kết luận. Vì cả hai đều thông minh, họ sẽ cố gắng không để đối thủ thắng ngay lập tức. Do đó, mỗi lượt chỉ xóa một quân cờ, người nào có thể xóa nhiều quân hơn sẽ thắng.

#include <iostream>
#include <string>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        string s;
        cin >> n >> s;
        s = '_' + s;

        bool hasWhite = false, hasBlack = false;
        for(char c: s.substr(1)){
            if(c == '1') hasWhite = true;
            else hasBlack = true;
        }
        if(!hasWhite || !hasBlack){
            cout << (hasWhite ? "Robin\n" : "Sunday\n");
            continue;
        }

        int blocks = 1;
        for(int i=1; i black ? "Robin\n" : "Sunday\n");
    }
    return 0;
}