All submissions for this problem are available.
There is a maze of size N*M, consisting of unit blocks. At the start Robot has RC percentage of battery charged.
Now Robot start from 1 st row and move towards N th row. From the present block robot can move to a block in the next row, which is either on right or on left side of the present block. On moving to a block in i th row j th column, Robots battery charge will reduce by C(i,j) percent if C(i,j) is greater then 0, else it will be recharged by C(i,j) percent.
For Example if battery has 50 percent of charge, on moving to block with C(i,j) = 15, battery will have 35 ( 50 -15 ) percent of the charge.
Now the task is to find out the status of the battery in the end, if the Robot moves optimally to save maximum charge. ( Remember : Battery Charge will not exceed more than 100 percent, and Robot will not move further if Battery charge goes down to 0 percent ).
First line of the input contains T, number of test cases.
In Each test case
First line consists of three space separated integers N, M and RC, representing values as described in the question.
Next N line contains M space separated Integers,( starting from 1 st row ). j th Integer in i th row is
C(i,j), charged gained or reduced on moving to i th row j th column in the maze.
For each test case print a single line containing single integer FC, maximum possible percentage of charge in the battery when Robot reaches N th row. If Robot can not reach the N th row then print -1.
- 1 <= T <= 10
- 1 <= N,M <= 500
- 0 <= RC <= 100
- -100 <= C(i,j) <= 100
Sample Input1 4 4 50 10 -10 10 -10 -10 10 -10 10 5 -5 5 -5 -5 -5 -5 -5
- One of the optimal move will be <1,2> -> <2,1> -> <3,2> -> <4,1>, in this move Robot gains 30 percent of the charge hence in the end Battery will have 80 percent of charge
|Time Limit:||0.190217 - 0.380435 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, CAML, ICK, BF, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.