Question: Fair Division
There was a terrorist attack in your area and terrosists walk along the roads robbing people. But they are some what reasonable that they allow you to keep half of the money you already have but only if you can divide it in half.
Example :- if you have 100 rupees you have to give terrorist 50 rupees and keep only 50 rupees to yourself. But this only happens if your currency is dividable. But we all know we have our money in the form of coins and notes. So if you have three rupees as 2 rupee coin and 1 rupee coin you can't divide it in half you have to give the two rupee coin to the terrorist.
So if a person having a amount which you can't divide it in half, terrorist will take more money. You notices that these terrorists doesn't have a good knowledge on mathematics. They can do only calculations in binary form. They also doesn't know that when adding two 1's together has a carry out in binary.
So after adding the last bit without the carry from the third bit, the final result is 36 (100100 in binary). in this case let's assume that a villager have 3 coins (21, 36, 49). so he can keep 70 by giving 36 to the terrorist because terrorist thinks that 49 + 21 is also 36.
Some More Examples
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56
Your task is to help town people by giving them chance to keep as much as money possible without letting terrorist know that people are having more money than a half of what they had early . You can give them values to split their money to two bags that terrorists think both have the same value. Given the amounts of all the coins a people has, people would like to know if this is possible; and, if it's possible, determine the maximum possible value they can save.
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 coins a people has. The next line contains the N integers Ci separated by single spaces, which denote the value of each coin a person has.
For each test case, output one line containing
TutorTeddy.com & Boston Predictive Analytics
[ Email your Statistics or Math problems to firstname.lastname@example.org (camera phone photos are OK) ]
Boston Office (Near MIT/Kendall 'T'):
Cambridge Innovation Center,
One Broadway, 14th Floor,
Cambridge, MA 02142,
Dallas Office (Near Galleria):
15950 Dallas Parkway,
Dallas, TX 75248,