TRIKA - Training for final


Abotrika is a famous player who plays in a good team. His team is going to play the final match next week and he have to train hard because all his fans are expecting that Abotrika will score more than one goal, so his team-mates suggested helping him in training given that Abotrika will play alone against all his friends in the training.

Input

Given two integers N,M (length and width of the training court) 2 <= N, M <= 20 and X,Y the starting point of Abotrika on the court where X is number of row and Y is number of column 1 <= X <= N, 1 <= Y <= M then P[i][j], where P is the power of each of his friends 0 < P[i][j] <100, and P[X][Y] is the power of Abotrika.

Output

The output must be one line either "N" or "Y" then the maximum power "Abotrika can get when he pass from his friends to reach the (the goal who is at the cell P[N][M] in the court ).

NOTE: Abotrika's power decreases by the power of his team-mate whom Aboutrika succeeded to get through on his way to score a goal. "Y" means that he had scored a goal with power at least 0 and "N" if he couldn't reach the goal with zero power at least. Also, Abotrika can only move in two directions -- right and down -- to reach the goal.

Example

Input:
4 4
1 1
100 55 10 2
20 10 90 1
60 20 22 4
1 30 70 5

Output:
Y 23

Explanation: The maximum power Abotrika can get after reaching goal : 100 - (55+10+2+1+4+5) = 23

Input:
2 2
1 1
1 55
20 10

Output:
N

Explanation: The maximum power Abotrika can get after reaching goal : 1 - (20+10) = -29 so it will be N.


hide comments
thichankitkat: 2022-01-30 08:22:43

Unable to solve with py3, bad input format, bad problem. Solve it by C++

sagar_june97p: 2019-06-11 13:48:42

AC in One go!!!

wytwalker: 2019-05-09 14:59:55

Similar to "Robot and Paths" on Codechef.

ajaytec227: 2018-08-01 14:16:02

The remaining power can also be zero

priyanshu_98: 2018-06-16 10:35:03

AC in second go. Must for Dp learner! otherwise this same as "SHOP - Shopping".

Last edit: 2018-06-16 10:41:47
tanmayak99: 2018-06-03 07:54:58

Take care of cases where x=n or y=m.. cost me 2 WAs.

Last edit: 2018-06-03 07:55:12
ameyanator: 2018-03-30 18:12:42

Simple DP problem! AC in one go

nadstratosfer: 2018-03-19 20:29:47

One of these problems where the hardest part is making out WTF the question itself is. Translation for those struggling to decipher the statement:

Input:
- on the first line 2 integers r, c : dimensions of the grid
- on the second line 2 integers xs, ys : Abotrika's location in the grid (1-indexed)
- r lines containing c integers each : description of the grid, each integer being the power of the player in that cell

Output:
Calculate the minimum-power-path from (xs, ys) to (r, c) while allowed to move only right or down. Print "Y x" where x is the difference between Abotrika's power and sum of powers in the path if x >= 0, else print "N".

Input contains blanklines, watch out when solving with Python.

vishesh_345: 2017-12-28 11:17:09

This is a specific case (move right and down) of a question which is done by dijkstra.
How to do if to find shortest path.

rohit9934: 2017-09-01 19:27:32

++149


Added by:Kawmia Institutes
Date:2010-08-22
Time limit:0.107s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 BF
Resource:Own problem