TUG - Tug of War
We want to pick a certain number of people from a group of N people and make them play a game of tug of war!
Then, we would like to split these people into two teams.
Afterwards, an intense game of tug of war would start.
However, when the strength of each team is not equivalent, the game is not very fun. A team's strength is the sum of the strengths of the people in the team.
Since you want the game that is fun, it is necessary to determine if it is possible to pick some people and split them into two teams such that the two teams' strengths are equal.
Input
The input consists of a number of test cases.
The first line is the number of test case, T. (1<=T<=200)
Each case starts with N (1<=N<=100,000), the total number of people.
The next line consists of N integers, separated by a space. The ith integer indicates the strength of the ith person. These integers are less than 100, but larger than 0.
Output
For each test case, output "YES" if it is possible to pick some people from the group and separate into two teams of equal strengths. If not, output "NO". Refer to the sample test cases for further clarifications.
Example
Input: 2
4
10 20 30 40
3
10 18 15 Output: YES
NO
There are a number of ways to pick teams for the first test case. One example would be {10,20} and {30}.
hide comments
kuderrahul:
2023-03-24 09:13:04
deceiving constraints Last edit: 2023-03-24 09:15:38 |
|
shimul58:
2021-09-06 01:25:29
pigeonhole principle && dp |
|
yfsyfs:
2020-03-15 17:25:37
knapsack seems does not work~ multiple knapsack with any optimate |
|
anirudnits:
2018-12-31 16:58:24
Similar problem of sorts ADACOINS, if you're using bitset that is! Have no idea as to how to do it otherwise, any suggestions? Last edit: 2018-12-31 17:00:04 |
|
vivek_dwivedi:
2018-06-28 16:01:25
Did it using bitset ! Happy coding ! |
|
aexpo:
2017-07-28 15:13:18
You can try this case:
|
|
Mukesh Yadav:
2012-11-28 17:48:46
finally ... but cost a lot of time coz of wrong assumption , I shd start looking quess much more carefully from now :(P)
|
|
Suresh Iyengar:
2011-06-24 15:40:54
Any hints to solve this problem?
|
|
Gurpreet Singh:
2011-06-16 18:38:46
Not exactly same but very similar to : http://www.codechef.com/problems/TEAMSEL/
|
Added by: | Lawl |
Date: | 2011-06-16 |
Time limit: | 1s-2.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |