| Submit | All submissions | Best solutions | Back to list |
BAT4 - BATMAN4 |
Batman: "A hero can be anyone. Even a man doing something as simple and reassuring as putting a coat around a little boy's shoulder to let him know that the world hadn't ended."
THE BOMB IS TRIGGERED !!, IT WOULD BLOW UP IN A FEW MINUTES !!
BATMAN resorts to his BAT and decides to head towards the ocean with the bomb.
However in front of him lies a huge grid of tall buildings. Starting from the top-leftmost grid he needs to move to the bottom right-most grid to reach the ocean. Since the fuel of BAT has nearly exhausted, BATMAN decides to chose a path where the maximum up distance travelled at a time is minimized. However, each movement of the BAT up or down the building takes one unit of time. (Horizontal movements can be made in no time). The clock keeps ticking, So BATMAN decides to choose a path reaching the destination minimizing the maximum up distance and with as much time left as possible.
Every Hero Has a Journey. Every Journey Has an End !
CatWoman : "You don't owe these people anymore. You've given them everything."
BatMan : "Not everything, not yet."
NOTES :
- BatMan requires to take the first jump on (1, 1)
- Print NO is no time is left.
- Minimum max up-distance is the first priority.
Input
The first line contains T, the number of test cases.
In each test case, the first line contains N (the size of the grid) and M (the time left).
The next N lines contain N integers, denoting the heights of the building.
Output
If BATMAN could reach the destination, print "YES", the maximum up distance travelled and the maximum time left with BATMAN.
If he could not reach the destination within time, print "NO".
Constraints
1 ≤ N ≤ 20
1 ≤ M ≤ 100
Example
Input: 1 3 40 2 4 3 4 5 3 2 4 6 Output: YES : 2 32
| Added by: | Romal Thoppilan |
| Date: | 2013-02-06 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | own problem |
hide comments
|
||||||
|
2017-01-04 18:07:25
spoj toolkit gives wrong answer for this question for some test cases |
||||||
|
2016-07-06 09:50:12
The problem is very easy and interesting however poorly worded. Do note that we have to minimize max-UP (but not down) distance. I kept trying to minimize max vertical distance and almost lost my mind due to WAs I was getting because of that. All the test case mentioned here and there couldn't detect my blunder. So please read this problem extra carefully. |
||||||
|
2016-07-05 00:58:51
height[i][j] < 2^10 AC with movement only right and down @Rohit kumar, I get YES : 12 76. Indicates weak test cases, I suppose. |
||||||
|
2016-07-01 18:25:45
What is the constraint on T and height[i][j]? Last edit: 2016-07-02 10:19:02 |
||||||
|
2016-06-09 22:47:32
ok so the maximum height difference is less than or equal to 14..I think that could have been increased to 10^6 to make the problem intresting Last edit: 2016-06-09 22:51:24 |
||||||
|
2015-07-20 09:43:32 Pramod
@parbays if test case is as follows what do you do ? 5 20 1 2 3 4 5 1000 1000 1000 1000 6 11 10 9 8 7 12 1000 1000 1000 1000 13 14 15 16 17 You need to go left also right to minimize maximum up distance? |
||||||
|
2014-03-25 00:22:09 viper
can you check my submission http://www.spoj.com/files/src/11320663/ Last edit: 2014-03-25 00:43:57 |
||||||
|
2014-02-01 09:49:42 parbays
@Eric, @Ujwal - Thats the intention of the prob to make u think that the max-up dis at a time (not overall) is achievable from only right and down move to propagate it. |
||||||
|
2013-10-30 15:27:08 Ryuzaki
What are the constraints on the height of the buildings ... Please comment. :) |
||||||
|
2013-10-30 15:04:38 Rohit kumar
what should be the o/p for :- 1 4 100 1 3 2 7 5 100 100 9 5 5 5 12 100 100 100 24 My AC solution is giving answer- YES : 12 74, But according to me the correct solution should be YES : 12 76. |
||||||
RSS