DCP-245: Escape from Grid-land Back to All Problems

Hard Search Techniques > Meet in the middle

You lost on the grid-land which is a square grid of size **N*N**, where each position of the grid contains some amount of gold on it. You are now standing on position (1, 1) .You want to escape from grid-land to go to your home. The moves you can perform are either **“one step right”** or **“one step down”** as long as you are inside the grid-land. ![enter image description here][1] To escape from grid-land you have to reach at position (N, N) of the grid by fulfilling a condition. The condition is that the multiplication of all golds taken at different positions of grid during the move must be less than or equal to **K**. Input: ------ Input starts with an integer **T (1<=T<=10)** , denoting the number of test cases. Each case contains an integer **N (2 ≤ N ≤ 16)** denoting the size of grid-land. The next N lines will contain N integer each separated by single space, denoting the gold on respective position of grid. Next line contain an integer K as described in the problem statement. The value of gold in grid cell and K will be a positive integer at most **10^18**. Output: ------- For each case of input, output an integer denoting total number of ways to escape from grid-land by using constraint as describe above.As answer could be very large output it modulo **1000000007** Sample Input ------------ 1 2 2 2 2 2 100 Sample Output ------------- 2 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/2bb5711a-9287-c4c3-d039-08d458052dd7_3e08b274ce994de7964626aa0bc286c9_W256xH276.png

Problem Setter:

Bishal Gautam

Please login to submit solution to this problem.

Problem Limits

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

Problem Stats




# User Language Timing
01 feodorv C 0.07s
02 I_See_You Cpp14 0.13s
03 BishalG Cpp14 0.20s
04 Morass Cpp14 0.21s
05 Robbinb1993 Cpp 0.21s
06 shahidul_brur Cpp 0.21s
07 shikhar Cpp14 0.21s
08 Zeronfinity Cpp14 0.22s
09 mahbubcseju Cpp14 0.28s
10 Al_Pacino Cpp 0.30s
11 sahedsohel Cpp14 0.32s
12 seyedssz Cpp14 0.42s
13 as_couple Cpp14 0.43s
14 mamun4122 Cpp14 0.44s
15 sayedgkm Cpp14 0.44s
16 lekato Cpp14 0.50s

Your feedback is our precious!

Or call +88 02 9853138 for support