坎迪·斯普利特 [英] C a n d y S p l i t t i n g

问题描述

问题

肖恩(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

推荐答案

如果您向我们展示您正在尝试，则将获得帮助(因为我帮助了 ^ ]).成为新手不是犯罪.仅发布作业要求不是一个有效的问题，并且使我们认为您只是懒惰，因此您将无法获得所需的答案.

自己尝试，开始编码.当您遇到问题然后再回来时，请使用改进问题"来添加您所做的代码和问题的说明，然后我们将很高兴帮助您理解错误并为您提供解决问题所需的信息. br/>
如果您不想尝试...，请阅读此 [

If you show us you are trying it, you will get help (as I helped this user[^]). Being newbie is not a crime. Just posting the requirements of your homework is not a valid question, and makes us think you are just lazy, so you won''t get the answers you are looking for.

Try it on your own, start coding. When you get a problem then come back, use "improve question" to add the code you did and a explanation of your problem, then we will be glad to help you understand you error and give you the needed information to solve your problem.

If you don''t want to try it... then please read this[^]

这是一个非常严重的问题.此问题是动态优化的经典示例.如果您是编程的新手，建议您将这个问题留给以后解决:)

This is very serious problem. This problem is a classic example for dynamic optimization. If you are new to the programming i suggest you to leave this problem for later solving :)

这篇关于坎迪·斯普利特的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！