DCP-201: Mr Papon and Nasir Back to All Problems

Hard Divide and Conquer > Dynamic Programming


Mr Papon doesn’t like Nasir at all. So he always try to give Nasir hard problem to solve. Today Mr Papon comes with knight and chess board problem. Given the size of the chess board ( **N X N** ) and initial position of the knight, what is the probability that after k moves the knight will be inside the chess board of **N X N** . Nasir isn’t very good at probability . Can you please help him. Note:- 1) The knight makes its all 8 possible moves with equal probability. 2) Once the knight is outside the chess board it cannot come back inside. ![enter image description here][1] 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 consists of two line. At first there are two integers N and K. and second there are two integers x , y which represents the initial position of the knight. Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the probability that after k moves the knight will be inside the chess board. Print answer with 4 decimal number after point. Check sample Input and Output for better understanding. Constraints: -------------- 1<= T <= 100 1 <= N <= 100 1 <= K <= 100 1 <= ( x , y ) <= N Sample Input ---------------- 2 8 3 3 5 10 3 2 4 Sample Output ------------- Case 1: 0.5742 Case 2: 0.4648 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/c587e5cf-af84-c11f-ba0d-08d40e38b120_3fcd62a33dbf4069b8e946ee44c11f61_W626xH264.png


Problem Setter:

Shakil Ahmed

Please login to submit solution to this problem.

Problem Limits

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

Problem Stats

34/77

Solve/Submission

Ranking

# User Language Timing
01 Morass Cpp14 0.01s
02 Robbinb1993 Cpp 0.02s
03 showmic Cpp 0.02s
04 feodorv C 0.09s
05 tariqiitju Cpp14 0.10s
06 nasif2587 Cpp14 0.19s
07 seyedssz Cpp14 0.20s
08 PKP_007 Cpp14 0.26s
09 Zeronfinity Cpp14 0.32s
10 sahedsohel Cpp14 0.35s
11 Mahmudul_Tushar Cpp14 0.40s
12 froghramar Cpp14 0.40s
13 kamrulashraf Cpp14 0.40s
14 habib_rahman Cpp14 0.41s
15 Tahseen Cpp14 0.44s
16 M3talicana Cpp14 0.44s
17 I_See_You Cpp14 0.48s
18 amin21 Cpp14 0.49s
19 akazad_cse13_ruet Cpp14 0.50s
20 fsshakkhor Cpp14 0.50s
21 ahqmrf Cpp14 0.57s
22 ssavi Cpp14 0.59s
23 Double_O Cpp14 0.60s
24 holahmeds Cpp14 0.62s
25 sayedgkm Cpp14 0.72s
26 shaft Cpp14 0.82s
27 Dariwala Cpp14 0.83s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support