STAR3CAS - THE WEIRD STAIRCASE

no tags 

You are given a representation of a stair case with 'N' steps (0 to n-1). In every step a number x[i] (for ith step) is written on it. At each step you have two choices. Either you can to proceed to next step (i + 1) or you can jump x[i] steps from that step (to i + x[i] th step). If the number written on the step is less than 0, you can come down that many number of steps or climb one step up.

Initially you are standing at the 0th step.

Find the minimum number of jumps needed to reach the top of the stair case.

If there is no way to reach the top of the stair case, print -1, else print the minimum number of jumps needed to reach the top of the staircase (nth step).

If a jump results in a step, which is greater than n, it is an invalid move.

Input

First line consists of 'T', the number of test cases. In every test case, the first line consists of 'n', the number of steps. The next line consists of n integers, x[0] to x[n-1].

Output

Print the minimum number of jumps required to reach the nth step. "Nth Step" is described in the problem statement.

Constraints

1 <= T <= 1000

1 <= n <= 20

-17 <= x[i] <= 17 and x[i] != 0

Example

Input:
2 
6 
-1 2 1 3 -3 3 
10 
5 1 1 1 6 -1 1 1 1 1 

Output:
3 
3

hide comments
Simes: 2023-02-28 09:50:47

Minor confusion, as the diagram shows, there are actually N+1 steps, 0 to N.

badboy_1496: 2018-07-19 15:54:48

solved with [spoiler]!!! ac in one go!!!

Last edit: 2018-08-22 15:59:33
nadstratosfer: 2018-03-27 06:38:36

The choice is always i+1, i+x[i], regardless of the value of x[i]. Like cegprakash said, this is not a greedy problem so don't follow 785227's comment; instead figure out what algo he might have confused BFS with.

jaideeppyne: 2017-08-19 05:36:30

Easy problem with [spoiler]. Take care of negative elements in the array. You need to iterate through the [spoiler] loop as many times as many negative numbers are present in the array.Happy Coding ! :D

Last edit: 2018-08-22 16:00:12
Sigma Kappa: 2017-06-25 11:56:37

Trivial.... should be moved to Tutorial. In place of this, tasks such as SPTTRN1-3 should be moved from tutorial to the classical.

Mostafa Ali Mansour: 2016-05-26 20:00:46

My first recursion prblm

Last edit: 2016-05-26 20:01:25
785227: 2014-06-19 12:48:19

My first ever bfs :)

cegprakash: 2014-06-19 12:48:19

Don't be greedy and take care of cycles.

pokemon: 2014-06-19 12:48:19

anymore test cases....?

cegprakash: 2014-06-19 12:48:19

check for upper/lower limits


Added by:cegprakash
Date:2013-03-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU