Montu the destroyer

All submissions for this problem are available.
Montu is a village destroyer. Now there are N settlements in a village , and every settlement has 8 houses. Every house is represented as a binary number. Two houses (a,b) or (b,a) [order does not matter] are connected if their binary representation differs by a bit.
Cost of destroying the village is total cost of all edges. Cost of each edge is initially 0 .But as usual a hero Nicks comes along to save his village , what he does is manipulates the cost array. He takes a random X (such that 0<=X<=7 ) for every settlement (of 8 houses). Then he multiplies the paths of houses excluding {X(mod8),X+1(mod8),X+2(mod8),X+3(mod8)} with “1” for every settlement.
Montu can destroy the village only if his compression power P , is greater than or equal to the (modified) cost of the village.
Input
First Line contains test case T. Each Test case contains 3 lines. First line of each test case contains N (no. of settlements) , second line contains N integers separated by a single space x1 , x1 …. xn. Third line contains Power P.
Output
Output answer to each testcase in a new line. YES if Montu can destroy the village and NO if he cannot.
Constraints
 N ≤ 40000 (is a power of 2)
 0 ≤ X ≤ 7
 1000 ≤ P ≤ 1000
 1 ≤ T ≤ 1000
Example
Input: 2 1 4 10 2 4 3 7 Output: YES NO1) In first test case you have 8 houses, the houses that are connected are
(0,1) , (0,2) , (0,4) , (1,3) , (1,5) , (2,3) , (2,6) , (3,7) , (4,5) , (4,6) , (5,7) , (6,7) And X=4 => cost of edge
(0,1),(0,2),(0,4),(1,3),(1,5),(2,3),(2,6),(3,7) are multiplied by 1.Thus the cost of village is 4 .
Hence Montu can destroy the village. 2) In case two the cost comes out to be 6 thus he CANNOT destroy the village.
Author:  insomnia_adm 
Tags  insomnia_adm 
Date Added:  20092013 
Time Limit:  0.3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 