Hard Search Techniques > Meet in the middle

Mr Papon is the coach of **"Nam diya kam nai"** IOI team and he doesn’t like Nasir at all. As one of the brightest contestant of **“Nam diya kam nai”** Nasir is very willing to participate this year IOI contest. Mr Papon doesn’t want nasir to be selected for this year IOI team so he is setting hard problem so that nasir won’t select for this year Team. For a given set of g integers where **G <= 40**. Each of them is at most **10^12**, determine the maximum sum subset having sum less than or equal to **S( 1 <= S <= 10^18)**. Nasir solved this problem and determined D is the answer for a given set G. But he is not sure , can you please help Nasir for that. If D is the highest subset sum for a given set G then print “The answer of Nasir is: right” otherwise print “The answer of Nasir is: wrong”. Input: ------ The first line contains an integer T( 1<= T <= 100 ) which denotes the number of Test cases. T test cases follow . Each test case contains two line of input. First line consists of three integer G, S and D and there are g integers number in the next line. Output: ------- For each test case, print a line **“Case x: y”** where x is replaced by the test case number and y will be replaced by string **“The answer of Nasir is: right”** if nasir's answer D is the highest subset sum less than or equal to S, otherwise print **“The answer of Nasir is: wrong”**. Sample Input ------------ 2 2 18468 6334 6335 26501 10 15725 15668 11479 29359 26963 24465 5706 28146 23282 16828 9962 492 Sample Output ------------- Case 1: The answer of Nasir is: wrong Case 2: The answer of Nasir is: right

Shakil Ahmed