Bài A: Tìm diện tích hình vuông

Bài toán yêu cầu tính diện tích của một hình vuông được xác định bởi bốn điểm. Do bốn điểm này tạo thành một hình vuông, khoảng cách giữa hai điểm kề nhau sẽ là cạnh của hình vuông. Do đó, chúng ta chỉ cần tìm một cặp điểm có cùng tọa độ x hoặc cùng tọa độ y, sau đó tính bình phương khoảng cách giữa chúng.

#include 
using namespace std;

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

    int soTest;
    cin >> soTest;

    while (soTest--) {
        int x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

        // Tìm cặp điểm có cùng tọa độ x (cạnh thẳng đứng) hoặc cùng tọa độ y (cạnh ngang)
        int canh = 0;
        if (x1 == x2 || x1 == x3 || x1 == x4) {
            // Tìm điểm thứ hai có cùng x với x1
            int x2_cung_x = (x2 == x1) ? x2 : (x3 == x1 ? x3 : x4);
            int y2_cung_x = (x2 == x1) ? y2 : (x3 == x1 ? y3 : y4);
            canh = abs(y1 - y2_cung_x);
        } else {
            // Tìm cặp điểm có cùng y
            int y2_cung_y = (y2 == y1) ? y2 : (y3 == y1 ? y3 : y4);
            canh = abs(x1 - ((y2 == y1) ? x2 : (y3 == y1 ? x3 : x4)));
        }

        cout << canh * canh << "
";
    }

    return 0;
}

Bài B: Biến đổi chuỗi nhị phân

Bài toán cho hai chuỗi nhị phân, cần tìm số thao tác tối thiểu để biến chuỗi thứ nhất thành chuỗi thứ hai. Một thao tác có thể là đổi một ký tự hoặc hoán đổi một ký tự '0' trong chuỗi thứ nhất với một ký tự '1' trong chuỗi thứ hai. Chiến lược tham lam ở đây là đếm số lượng ký tự '0' và '1' không khớp. Chúng ta có thể hoán đổi một cặp '0' và '1' không khớp để sửa hai vị trí cùng một lúc. Số thao tác tối thiểu sẽ là số cặp có thể hoán đổi cộng với số ký tự còn lại cần phải đổi.

#include 
using namespace std;

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

    int soTest;
    cin >> soTest;

    while (soTest--) {
        int do_dai;
        cin >> do_dai;
        string chuoi1, chuoi2;
        cin >> chuoi1 >> chuoi2;

        if (chuoi1 == chuoi2) {
            cout << 0 << "
";
            continue;
        }

        int dem_0 = 0, dem_1 = 0;
        for (int i = 0; i < do_dai; ++i) {
            if (chuoi1[i] != chuoi2[i]) {
                if (chuoi1[i] == '1') dem_1++;
                else dem_0++;
            }
        }

        // Số thao tác tối thiểu: số cặp có thể hoán đổi + số ký tự còn lại
        int ket_qua = min(dem_0, dem_1) + abs(dem_0 - dem_1);
        cout << ket_qua << "
";
    }

    return 0;
}

Bài C: Quản lý pin điện thoại

Bài toán mô phỏng việc quản lý pin của điện thoại. Điện thoại có pin ban đầu là `f` và nhận `n` tin nhắn tại các thời điểm `t[i]`. Giữa các tin nhắn, điện thoại có thể ở chế độ chờ (tiêu thụ `a` pin mỗi đơn vị thời gian) hoặc tắt rồi bật lại (tiêu thụ `b` pin). Cần xác định xem pin có đủ để sử dụng trong suốt quá trình không. Chiến lược tham lam là, với mỗi khoảng thời gian giữa hai tin nhắn, chọn cách tiêu thụ pin ít hơn giữa hai lựa chọn.

#include 
using namespace std;

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

    int soTest;
    cin >> soTest;

    while (soTest--) {
        long long so_tin_nhan, pin_dau, muc_tieu_hao, muc_tieu_hao_khoi_dong;
        cin >> so_tin_nhan >> pin_dau >> muc_tieu_hao >> muc_tieu_hao_khoi_dong;

        vector<long long> thoi_gian(so_tin_nhan + 1);
        for (int i = 1; i <= so_tin_nhan; ++i) {
            cin >> thoi_gian[i];
        }

        for (int i = 1; i <= so_tin_nhan; ++i) {
            if (pin_dau <= 0) break;
            long long khoang_cach_thoi_gian = thoi_gian[i] - thoi_gian[i - 1];
            pin_dau -= min(khoang_cach_thoi_gian * muc_tieu_hao, muc_tieu_hao_khoi_dong);
        }

        cout << (pin_dau > 0 ? "YES" : "NO") << "
";
    }

    return 0;
}

Bài D: Tối đa hóa tổng chênh lệch tuyệt đối

Bài toán yêu cầu tạo một mảng mới `c` từ hai mảng `a` và `b` sao cho tổng các chênh lệch tuyệt đối giữa các phần tử liên tiếp `|c[i] - c[i+1]|` là lớn nhất. Bằng cách sắp xếp hai mảng, ta có thể áp dụng chiến lược tham lam: ghép cặp phần tử nhỏ nhất của một mảng với phần tử lớn nhất của mảng còn lại và ngược lại, sau đó chọn cặp có chênh lệch lớn hơn ở mỗi bước.

#include 
using namespace std;

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

    int soTest;
    cin >> soTest;

    while (soTest--) {
        int kich_thuocA, kich_thuocB;
        cin >> kich_thuocA >> kich_thuocB;

        vector<long long> mangA(kich_thuocA);
        vector<long long> mangB(kich_thuocB);
        for (auto &x : mangA) cin >> x;
        for (auto &x : mangB) cin >> x;

        sort(mangA.begin(), mangA.end());
        sort(mangB.begin(), mangB.end());

        long long tong = 0;
        int traiA = 0, phaiA = kich_thuocA - 1;
        int traiB = 0, phaiB = kich_thuocB - 1;

        for (int i = 0; i < kich_thuocA; ++i) {
            long long chenh_lech1 = abs(mangA[traiA] - mangB[phaiB]);
            long long chenh_lech2 = abs(mangA[phaiA] - mangB[traiB]);

            if (chenh_lech1 >= chenh_lech2) {
                tong += chenh_lech1;
                traiA++;
                phaiB--;
            } else {
                tong += chenh_lech2;
                phaiA--;
                traiB++;
            }
        }

        cout << tong << "
";
    }

    return 0;
}