ZeroJudge E559: Luggage

UVa 10664 – Luggage

Peter and his friends are on vacation, and they’ve decided to drive to northern Spain. There are seven of them in total, and they believe two cars are enough to fit all their luggage.
It’s time to go! Time to hit the road.
However, the drivers have different opinions about which suitcase should go into which trunk because no one wants their car to carry more weight (as it increases fuel consumption).
How can the luggage be distributed so that both cars carry the same total weight? (The drivers cannot split or repack any luggage!)
Each suitcase has a label M indicating its weight.
If possible, please help them distribute the luggage evenly between the two cars.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input’s first line contains an integer T, representing the number of test cases.
Each test case is provided on a separate line and consists of N integers (1 ≤ N ≤ 20).
These integers represent the weight M of each suitcase (0 < M ≤ 200).		For each test case:
•If it is possible to distribute the luggage such that the total weight carried by the two cars is equal, output “YES”.
•Otherwise, output “NO”.
3
1 2 1 2 1
2 3 4 1 2 5 10 50 3 50
3 5 2 7 1 7 5 2 8 9 1 25 15 8 3 1 38 45 8 1		NO
YES
YES

Thought Process

Use a string to receive the input data, split it into an array of integers, and follow these steps:
1. Calculate the total weight of all luggage.
2. If the total weight is odd, directly output “NO” (as it’s impossible to split it equally).
3. Otherwise, calculate half of the total weight, which is the target weight for one car.
• If one subset of luggage can achieve this target weight, output “YES” (since the other subset will automatically have the same weight).
• If not, output “NO”.

Declare a Map to store the numbers or sums that have occurred. Iterate through each number in the array, and for each number, run an inner loop from half of the total weight to the current number. If Map[current number - current element] > 0, increment Map[current number]. Finally, also increment Map[current element].

If Map[half] > 0, it means the luggage can be evenly divided. Otherwise, it cannot be divided equally.

Sample Code－ZeroJudge E559: Luggage

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    cin.ignore();
    for (int i = 0; i<T; i++) {
        string str;
        getline(cin, str);
        string add = "";
        vector<int>v;
        int sum = 0;

        for (int j = 0; j<str.length(); j++) {
            const char ch = str[j];
            if (ch == ' ') {
                int toInt;
                if (add.length() == 1) toInt = add[0] - '0';
                else toInt = stoi(add);
                sum += toInt;
                v.push_back(toInt);
                add = "";
                continue;
            }
            add += ch;
        }
        if (add.length() > 0) {
            int tmp;
            if (add.length() == 1) tmp = add[0] - '0';
            else tmp = stoi(add);
            sum += tmp;
            v.push_back(tmp);
        }
        if (sum % 2 != 0) cout << "NO\n";
        else {
            const int half = sum / 2;
            unordered_map<int, int>MAP;
            for (int i = 0; i<v.size(); i++) {
                const int tmp = v[i];
                for (int j = half; j>=tmp; j--) {
                    if (MAP[j-tmp] > 0) MAP[j]++;
                }
                MAP[tmp]++;
            }
            if (MAP[half] > 0) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

//ZeroJudge E559
//Dr. SeanXD
Tags

Related Posts

Comments