All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Easy Maze Problem
Tag(s):
No tags
Problem
Editorial
Analytics

Alice challenges Bob to cross her Maze. 

The Maze is in the form of a rectangular grid. where there are M+1 levels numbered from 0-M and each level has N+1  doors numbered from 0 - N, all the doors lead to the same upper level.

Alice is confident that she doesn’t need to add any traps to the maze and Bob is still going to fail to cross it. Each door of level  ‘i’ leads to the next level 'i+1' and it is possible to travel vertically at the current level without restrictions. 

But Bob is a cautious guy, and he suspects some of the doors must be trapped. So he has formulated a plan to cross the Maze, his plan is an array of Integers C, which tells him which possible doors he can choose at each level. At each level i where 1 <=i<=M C[i] denotes the absolute difference between Bob’s previous choice of the door (the door through which he entered the current level) and the current door that he can take. Eg, if he took door 5 at level i-1, and C[i] is 4, then he must take either door number 5+4 = 9  or  5-4= 1, at this level. He can never go outside the grid.  

Bob always chooses his lucky number Bth Door when he enters the Maze at level 0.

Count and print the number of doors from which Bob can possibly exit the Maze at the Mth level, or print -1 if it impossible for Bob to exit given his current plan. 


INPUT

The first line of input contains N and M. 

The second line of input contains a single integer B, Bob's lucky number

The third line of input contains M integers of array C[] where  1<=i<=M, C[i] indicated the absolute difference of the door number Bob can take at level i and the door he took at level i-1.  


OUTPUT

A single integer indicating the number of possible doors Bob can exit level M or print -1 if it is impossible for Bob to exit the Maze following his plan.


CONSTRSAINTS

1<=N<=1000

1<=M<=1000

0<=B<= N

 

SAMPLE INPUT
4 4
0
2 1 2 1
SAMPLE OUTPUT
3
Explanation

Bob enters the Maze at level  0 through door 0. 

At level 1 C[1]= 2, So he can choose only door 2 to move to the next level.

At level 2 C[2]= 1, So he can choose door 3 or 1

At level 3 C[3]=2, He can choose door 1 or 3

At level 4 C[4]= 1, Similarly at level 4 he can pass through door 0,2 or 4 at level 4. 
So the answer is 3.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?