Time Limit: 1s
Memory Limit: 128MB
Just as the title indicates, this problem is pretty simple. Given you a truth Table of a logic function and you can express it with a sum of product form which product’s priority is higher than sum (Like ) here ‘∧’ means logic gate “and”, ‘∨’ means the logic gate “or”, and ‘¬’ means the logic gate “not”, and the cost of this function is
2 * 2 + 3 = 7 (two “and” gate with 2 inputs, one “and” gate with 3 inputs, here we just consider “and” gates’ costs)
But we can simplify it to a better form like as we all know, and cost is just 4, so the question is how you gain a minimum cost of a logic function which described by a truth table. Truth table is defined as follow:
x1 x2 x1∧x2
0 0 0
0 1 0
1 0 0
1 1 1
The cost is the sum of inputs of all “and” gates.
First an integer T witch means the number of test cases, and then followed by T cases.
The first line of each case is an integer n which means the number of logic variable, then an integer m indicates how much ‘1’(true) outputs in the truth table of the logic function followed by a line has m integer a[i] denote the decimal form inputs for the logic function returns 1(true).
(1<= T <= 10)
(1<= n <= 8)
(1<= m <=50)
(0<= a[i] <2^{n})
An integer denote the minimum cost of the logic function (note if logic function always return 0 or 1,then just output 0 means no “and” gate needed)
2 2 1 3 4 9 7 8 9 10 11 12 13 14 15
2 4
The first case exactly defined function “and” (x1∧x2),
F(1,1) = 1
The second case is the example show in the problem (x1∨(x2∧x3∧x4))
F(0,1,1,1) = 1
F(1,0,0,0) = 1
F(1,0,0,1) = 1
F(1,0,1,0) = 1
F(1,0,1,1) = 1
F(1,1,0,0) = 1
F(1,1,0,1) = 1
F(1,1,1,1) = 1