Purple Lights
Historically, the colour purple has been associated with royalty, magic, eggplants and a rather suspicious dinosaur whose name rhymes with 'arnie'. Mark, in anticipation of fulfilling his dream of ruling the galaxy for the next millennium is throwing the most purple party possible to reflect his royal-magic.
Mark in his haste to throw the galaxy's best gathering hastily ordered 'purple-range' lights. When they arrived, they turned out to be rather peculiar bulbs indeed. Instead of being purple when turned on, each bulb can either be turned on in 'blue' or 'red' mode (usually with differing brightness). A lighting scheme will consist of switching some bulbs blue and the rest red. The total amount of blue-light is the sum of the blue-brightness of the bulbs set to blue and similarly the total amount of red-light is the sum of the red-brightness of the bulbs set to red.
You have been tasked with creating the most purple lighting scheme possible with the bulbs provided (lest your days are numbered). This means given some number of 'purple-range' bulbs you must find the most purple combination of switching some of the lights blue and the others red.
Mark hates detail, so he only wants to know how 'close' to purple you can make the overall lighting scheme (that is, the smallest absolute difference possible between total blue and red light).
Input Specification
The first line contains an integer \(t\) (\(1 \leq t \leq 10\)), the number of test cases to follow. The first line of each test case will contain an integer \(n\) (\(1 \leq n \leq 16\)), how many 'purple-range' bulbs are present. The following \(n\) lines will each contain two integers \(b_{i}, r_{i}\) (\(0 \leq b_{i},r_{i} \leq 10^6\)), the first being the brightness of blue-light and the second being the brightness of red-light (of the \(i\)th bulb).
Output Specification
For each each test case, output a single integer on a single line; the smallest absolute difference possible between red and blue light.
Sample Input
2
2
10 20
20 10
3
4 0
0 1
0 1Sample Output
0
0
Comments
I'm confused. It says n is 3 in the sample input but there are 4 lines following the 3. Help plz.
I can't see any problem with the sample input/output. I'll quickly go through it line by line:
This is \(t\). This means that the number of test cases is two.
This is the first sample test case. The two at the top (\(n\)) indicates the number of lines that follow. Each row below that has \(b_i\) and \(r_i\).
This is second sample test case. Here we can see that \(n\) is \(3\), and as such there are three lines following it, each containing \(b_i\) and \(r_i\).