问题描述
问题
肖恩(Sean)和帕特里克(Patrick)是兄弟，他们刚刚从父母那里得到了一袋精美的糖果.每块糖果都有一些正整数值，孩子们想在它们之间进行划分.首先，肖恩将糖果分成两堆，然后选择其中一堆送给帕特里克(Patrick).然后，帕特里克(Patrick)将尝试计算每堆糖果的价值，其中一堆糖果的价值是该糖果堆中所有糖果的价值之和；如果他认为这些桩的价值不相等，他就会哭泣.
不幸的是，帕特里克还很年轻，不知道如何正确添加.他几乎知道如何将二进制数字相加.但是当他将两个1加在一起时，他总是忘记将余数带到下一位.例如，如果他想对12(二进制1100)和5(二进制101)求和，他将正确地将最右边的两个位相加，但是在第三位他将忘记将余数携带到下一位:
1100
+ 0101
------
1001
因此，在将最后一位与第三位不加进位相加之后，最终结果为9(二进制1001).以下是Patrick的数学技巧的其他一些例子:
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56
肖恩(Sean)善于补充，他想尽可能多地利用自己的价值，而又不要让他的弟弟哭泣.如果可能的话，他会将一袋糖果分成两堆非空的糖果，以使帕特里克认为两者具有相同的价值.给定袋子中所有糖果的价值，我们想知道是否有可能；并尽可能确定Sean桩的最大可能值.
输入
输入的第一行给出了测试用例的数量，T.T测试用例紧随其后.每个测试用例用两行描述.第一行包含一个整数N，表示袋子中糖果的数量.下一行包含N个由单个空格分隔的整数Ci，表示袋子中每块糖果的价值.
输出
对于每个测试用例，输出包含"Case #x:y"的一行，其中x是案例编号(从1开始).如果Sean不可能阻止Patrick哭泣，则y应该是否".否则，y应该是肖恩将保留的一堆糖果的值.
极限
1≤T≤100.
1≤Ci≤106.
小型数据集
2≤N≤15.
大型数据集
2≤N≤1000.
样品
输入输出
2种情况#1:否
5种情况#2:11
1 2 3 4 5
3
3 5 6
Problem
Sean and Patrick are brothers who just got a nice bag of candy from their parents. Each piece of candy has some positive integer value, and the children want to divide the candy between them. First, Sean will split the candy into two piles, and choose one to give to Patrick. Then Patrick will try to calculate the value of each pile, where the value of a pile is the sum of the values of all pieces of candy in that pile; if he decides the piles don''t have equal value, he will start crying.
Unfortunately, Patrick is very young and doesn''t know how to add properly. He almost knows how to add numbers in binary; but when he adds two 1s together, he always forgets to carry the remainder to the next bit. For example, if he wants to sum 12 (1100 in binary) and 5 (101 in binary), he will add the two rightmost bits correctly, but in the third bit he will forget to carry the remainder to the next bit:
1100
+ 0101
------
1001
So after adding the last bit without the carry from the third bit, the final result is 9 (1001 in binary). Here are some other examples of Patrick''s math skills:
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56
Sean is very good at adding, and he wants to take as much value as he can without causing his little brother to cry. If it''s possible, he will split the bag of candy into two non-empty piles such that Patrick thinks that both have the same value. Given the values of all pieces of candy in the bag, we would like to know if this is possible; and, if it''s possible, determine the maximum possible value of Sean''s pile.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described in two lines. The first line contains a single integer N, denoting the number of candies in the bag. The next line contains the N integers Ci separated by single spaces, which denote the value of each piece of candy in the bag.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1). If it is impossible for Sean to keep Patrick from crying, y should be the word "NO". Otherwise, y should be the value of the pile of candies that Sean will keep.
Limits
1 ≤ T ≤ 100.
1 ≤ Ci ≤ 106.
Small dataset
2 ≤ N ≤ 15.
Large dataset
2 ≤ N ≤ 1000.
Sample
Input Output
2 Case #1: NO
5 Case #2: 11
1 2 3 4 5
3
3 5 6
推荐答案
这篇关于坎迪·斯普利特的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！