DCP-256: Mr Papon as IOI coach Back to All Problems

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

Problem Setter:

Shakil Ahmed

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 8.00
C++ 8.00
C++14 8.00
C# 9.00
Go 9.00
Java 9.00
JavaScript 9.00
Objective-C 9.00
Perl 9.00
PHP 9.00
Python 9.00
Python3 9.00
Ruby 9.00
VB.Net 9.00

Problem Stats




# User Language Timing
01 a_rahman Cpp14 0.19s
02 Morass Cpp14 0.21s
03 Foyaz05 Cpp14 0.21s
04 sayedgkm Cpp14 0.21s
05 swapnilsaha Cpp14 0.35s
06 feodorv Cpp14 0.47s
07 Robbinb1993 Cpp14 0.94s
08 tariqiitju Cpp 1.41s
09 BishalG Cpp14 1.50s
10 sahedsohel Cpp14 2.18s
11 Al_Pacino Cpp14 3.76s
12 nchack Python3 4.02s
13 seyedssz Cpp14 4.62s
14 khatribiru Cpp14 5.69s
15 S_A_Babaei Cpp 5.99s
16 swapnil Cpp14 6.88s
17 mahbub07 Cpp14 6.91s
18 clkjwdhc Cpp 6.93s
19 oneshadab Cpp14 7.29s
20 ssavi Cpp14 7.37s
21 I_See_You Cpp14 7.58s
22 lekato Cpp14 7.61s
23 showmic Cpp14 7.64s

Your feedback is our precious!

Or call +88 02 9853138 for support