Bài toán A - Phân Chia Mảng Không Chia Hết

Bài toán yêu cầu chúng ta phân chia các phần tử từ một mảng gốc a vào hai mảng mới là b và c. Điều kiện bắt buộc là không được tồn tại bất kỳ cặp phần tử nào sao cho một số thuộc mảng b chia hết cho một số thuộc mảng c. Kết quả cần xuất ra kích thước của hai mảng mới cùng với các phần tử tương ứng.

Phân Tích Giải Thuật

Đây là một dạng bài toán xây dựng (constructive) điển hình. Để đảm bảo điều kiện không chia hết, một cách tiếp cận đơn giản nhất là làm cho mọi phần tử trong mảng c đều lớn hơn mọi phần tử trong mảng b. Khi đó, phép chia lấy dư sẽ luôn trả về chính số bị chia (khác 0).

Chiến lược cụ thể như sau:

• Sắp xếp mảng ban đầu theo thứ tự tăng dần.
• Kiểm tra trường hợp vô nghiệm: Nếu tất cả các phần tử trong mảng đều bằng nhau, ta không thể phân chia thỏa mãn điều kiện, khi đó xuất ra -1.
• Nếu có nghiệm, ta đưa tất cả các phần tử nhỏ hơn giá trị lớn nhất vào mảng b, và các phần tử bằng giá trị lớn nhất vào mảng c.

Cách phân chia này đảm bảo mọi phần tử trong c đều lớn hơn mọi phần tử trong b, do đó không có phép chia hết nào xảy ra.

Triển Khai Mã Nguồn

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

void solve() {
    int sz;
    cin >> sz;
    vector<int> elements(sz);
    for (int i = 0; i < sz; ++i) {
        cin >> elements[i];
    }
    
    sort(elements.begin(), elements.end());
    
    // Kiểm tra trường hợp tất cả phần tử bằng nhau
    if (elements.front() == elements.back()) {
        cout << "-1" << endl;
        return;
    }
    
    vector<int> groupB, groupC;
    int maxVal = elements.back();
    
    for (int val : elements) {
        if (val != maxVal) {
            groupB.push_back(val);
        } else {
            groupC.push_back(val);
        }
    }
    
    cout << groupB.size() << " " << groupC.size() << endl;
    for (int i = 0; i < groupB.size(); ++i) {
        cout << groupB[i] << (i == groupB.size() - 1 ? "" : " ");
    }
    cout << endl;
    for (int i = 0; i < groupC.size(); ++i) {
        cout << groupC[i] << (i == groupC.size() - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}

Bài toán B - Tối Ưu Hóa Tổng Giá Trị Nhỏ Nhất

Cho trước m mảng số nguyên. Với mỗi mảng, chúng ta được phép thực hiện tối đa một thao tác: di chuyển một phần tử bất kỳ từ mảng này sang một mảng khác. Mục tiêu là sau khi thực hiện các thao tác (hoặc không thực hiện), tổng giá trị nhỏ nhất của tất cả các mảng là lớn nhất có thể.

Phân Tích Giải Thuật

Để tối ưu hóa tổng các giá trị minimum, chúng ta cần xem xét đóng góp của các phần tử trong mỗi mảng. Nhận thấy rằng:

1. Giá trị nhỏ nhất toàn cục (global minimum) trong tất cả các mảng chắc chắn sẽ đóng góp vào kết quả cuối cùng, vì dù di chuyển đi đâu, nó vẫn là nhỏ nhất của mảng chứa nó.
2. Đối với mỗi mảng, chỉ có hai ứng viên tiềm năng cho giá trị minimum sau cùng: phần tử nhỏ nhất hiện tại hoặc phần tử nhỏ thứ hai (nếu phần tử nhỏ nhất bị di chuyển đi).
3. Chiến lược tối ưu là giữ lại giá trị nhỏ nhất toàn cục tại mảng chứa nó. Đối với tất cả các mảng còn lại, ta di chuyển phần tử nhỏ nhất của chúng sang mảng chứa global minimum. Khi đó, giá trị minimum của các mảng này sẽ trở thành phần tử nhỏ thứ hai ban đầu của chúng.

Kết quả cuối cùng sẽ bằng: Global Minimum + Tổng (Phần tử nhỏ thứ hai của tất cả các mảng còn lại).

Triển Khai Mã Nguồn

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

void solve() {
    int numArrays;
    cin >> numArrays;
    
    vector<vector<int>> grid(numArrays);
    int globalMinVal = INT_MAX;
    int globalMinIndex = -1;
    
    for (int i = 0; i < numArrays; ++i) {
        int k;
        cin >> k;
        grid[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> grid[i][j];
        }
        // Sắp xếp từng mảng để dễ tìm min và second min
        sort(grid[i].begin(), grid[i].end());
        
        if (grid[i][0] < globalMinVal) {
            globalMinVal = grid[i][0];
            globalMinIndex = i;
        }
    }
    
    long long totalSum = 0;
    // Cộng global minimum vào tổng
    totalSum += globalMinVal;
    
    for (int i = 0; i < numArrays; ++i) {
        if (i == globalMinIndex) {
            continue; // Mảng chứa global min đã được tính
        }
        // Các mảng khác đóng góp bằng phần tử nhỏ thứ 2
        // Giả sử mỗi mảng có ít nhất 2 phần tử theo ngữ cảnh bài toán
        if (grid[i].size() > 1) {
            totalSum += grid[i][1];
        } else {
            totalSum += grid[i][0]; 
        }
    }
    
    cout << totalSum << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}