Loading...
Loading...
Loading...
On sports day, the juniors play a hopping game on a straight line of n stones. Each stone has a number painted on it. From stone i with number a[i], you may jump forward to any of the next a[i] stones. A stone with 0 lets you go nowhere.
You start on stone 1. Print YES if you can reach stone n. Otherwise print NO and the number of the farthest stone you can reach.
YES, or NO k where k is the farthest stone you can reach.Example 1
Input
5 2 3 1 1 4
Output
YES
Jump from stone 1 to stone 2, then 3 stones forward to stone 5.
Example 2
Input
5 3 2 1 0 4
Output
NO 4
Stones 1, 2 and 3 can only reach up to stone 4, and stone 4 has 0. So stone 5 is never reached.
Try the problem first. Open one hint at a time.
You do not need the exact path. You only need to know how far you could get.
Keep the farthest stone you can reach so far. Walk through the stones from the start.
You may use a stone only if it is within the farthest reach so far. Then update the reach with how far that stone lets you jump.
When the walk stops, compare the reach with the last stone.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor