7996: CodeChef BOOKPAGES - Divide Pages
[Creator : ]
Description
Chef has N books such that the i-th book has $A_i$ pages. He wants to divide all the books between Alice and Bob such that:
- Both Alice and Bob get at least one book;
- The number of pages allotted to Alice and Bob are either both odd or both even.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer N — the number of books.
The next line contains N space-separated integers, where the i-th integer denotes the number of pages in the i-th book.
Each test case consists of multiple lines of input.
The first line of each test case contains a single integer N — the number of books.
The next line contains N space-separated integers, where the i-th integer denotes the number of pages in the i-th book.
Output
For each test case, output on a new line, YES, if a valid distribution exists. Otherwise, print NO.
Constraints
1≤T≤100
$2≤N≤10^5$
$1≤A_i≤100$
The sum of N over all test cases won't exceed $2⋅10^5$.
$2≤N≤10^5$
$1≤A_i≤100$
The sum of N over all test cases won't exceed $2⋅10^5$.
Sample 1 Input
3
3
2 4 6
4
1 1 2 3
6
3 1 1 1 1 1
Sample 1 Output
YES
NO
YES
Test case 1: Consider the distribution where Alice gets books 1 and 3, and Bob gets the book 2. Thus, the number of pages allotted to Alice is 2+6=8, and the number of pages allotted to Bob is 4. Thus, both Alice and Bob have even number of pages allotted to them.
Test case 2: It can be proven that there exists no valid distribution.
Test case 3: Consider the distribution where Alice gets the books 1,2, and 3, and Bob gets the books 4,5, and 6. Thus, the number of pages allotted to Alice is 3+1+1=5, and the number of pages allotted to Bob is 1+1+1=3. Thus, both Alice and Bob have odd number of pages allotted to them.
Test case 2: It can be proven that there exists no valid distribution.
Test case 3: Consider the distribution where Alice gets the books 1,2, and 3, and Bob gets the books 4,5, and 6. Thus, the number of pages allotted to Alice is 3+1+1=5, and the number of pages allotted to Bob is 1+1+1=3. Thus, both Alice and Bob have odd number of pages allotted to them.