ZeroJudge B116: Plus and Minus

Assume there are N positive integers A[1], A[2], …, A[N]. We need to add either a + sign or a - sign before each number so that their total sum is 0.

For example, with the numbers 1, 2, and 3, we can achieve (-1) + (-2) + (+3) = 0. However, for the numbers 2, 2, and 1, it is impossible to make their total sum 0 by adding + or - signs.

Please write a program to determine whether it is possible to make the sum of any N positive integers equal to 0 by adding + or - signs in front of each number.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line of the input file contains two positive integers, M and N, separated by a space. M represents the number of test cases, and each test case contains N positive integers.
From the second line to the M+1th line, each line contains the specified N positive integers, separated by spaces. Here, 0 < M ≤ 10, and 0 < N ≤ 100.		For each test case, if it is possible to add + or - signs in front of the integers to make their total sum 0, please output "Yes"; otherwise, output "No".
4 3
1 2 3
3 2 1
2 2 2
5 1 6
2 8
1 2 3 4 5 6 7 8
12 12 10 11 34 22 33 26		Yes
Yes
No
Yes
Yes
Yes
ZeroJudge B116 Sample Test Case

Thought Process

This problem essentially requires finding two identical numbers. Therefore, if the total sum of the numbers is odd, you can directly output "No".

Using the DFS method to exhaustively add the numbers, if a combination of numbers sums to half of the total sum, it means that the remaining numbers will also sum to half of the total sum. Therefore, the goal is to find whether there is a combination that can sum to half of the total sum.

Sample Code－ZeroJudge B116: Plus and Minus

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

bool ok = false;
int sum = 0;

void DFS(vector<int>num, int index, int count) {
    if (ok || count > sum/2) return;
    if (count == sum/2) {
        ok = true;
        return;
    }
    if (index == num.size()) return;
    for (int i = index; i<num.size(); i++) {
        DFS(num, index+1, count+num[i]);
        if(ok) return;
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int M, N;
    while (cin >> M >> N) {
        for (int i = 0; i<M; i++) {
            vector<int>num;
            int max = -999999;
            sum = 0;
            for (int j = 0; j<N; j++) {
                int tmp;
                cin >> tmp;
                sum += tmp;
                if (tmp > max) max = tmp;
                num.push_back(tmp);
            }
            if (sum/2 < max || sum % 2 == 1) {
                cout << "No\n";
                continue;
            }
            ok = false;
            DFS(num, 0, 0);
            if (ok) {
                cout << "Yes\n";
                continue;
            }
            cout << "No\n";
        }
    }
}

//ZeroJudge B116
//Dr. SeanXD
Tags

Related Posts

Comments