The Prince's Path
Challenge created by conioh
Note the clarification below
The Prince of Zakarta has a problem. The princess has been kidnapped by the demon. To save the princess he needs to travel through a path similar to figure below, where each line leads to different cities denoted by circles.
At most cities he faces two paths to two different cities. But in the bottom row, there's only one path forward to the end.
In each city the Prince will either find a devil power or good power. The Prince will initially start with the power of the first city he visits. If he passes the city with devil power d
then his power will be reduced by d
i.e. P - d. Similarly, if he passes the city with good power g
his power will be increased by g
i.e. P + g.
If, after the first city, his power ever becomes 0 or less, he will Die. The Prince has all the information needed, but he needs your help to tell him whether he can save the Princess.
Clarification: The Prince can start at any city on the left side, even if it's not greater than 0. He only dies if he hits 0 or below at any point afterwards.
I/O format
The first line of input contains c
, the number of test cases. c
cases follow, with each case in the following format:
- The first line contains
n
, the number of cities from with which he can start. - The next line contains
m
, the number of cities in each path. - In each of the next
n
lines there will bem
integers i.e. powers. - A positive power denotes a good power and a negative power denotes an evil power.
Output a YES
or NO
for each case:
YES
if he can save princess.
NO
if he can’t.
Example
Input:
3 4 4 2 3 -12 2 1 4 -10 2 0 5 -9
Output:
YES
Explanation:
He can follow this path (0,0) -> (1,1) - > (2,2) -> (3,2)
So his power at the end = 4 + 1 + 5 - 9 = 1
And at every instance it is greater than 0.
Constraints
There can be up to 100 cases in a challenge. Each case can have up to 200 cities.
Challenge
Can the Prince save the Princess? Output Yes
or No
.
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
Egor Kulikov
May 26, 10:13 AM"The Prince will initially start with power P." It is not given in itput. What its value?
Learneroo
May 26, 10:26 AM@Egor, he will start with the power of the first city he visits. Sorry for the confusion.
Fred Spieler
May 26, 1:19 PMThe first line of input contains the number of test cases... kind of matters...
Fred Spieler
May 26, 1:39 PMHmm... I pass the test input but not contest input... possibly something wrong with this problem?
Learneroo
May 26, 1:41 PMSorry, the challenge has been clarified, see above. Next time you're hired as reviewers!
James Smith
May 26, 11:15 PMSo wait, can he start from only the top-left city at (0, 0)? Or could he start at any city on the left side?
Learneroo
May 26, 11:17 PM@James, he can start any city on the left side, as shown in the picture on top.