Shopping Mall Design

Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Antoni is designing a new shopping mall! It is comprised of \(n\) cells numbered from \(1\) to \(n\) in a line. Of course, customers want to visit many different stores.

So, Matt has designed a transportation system to move people between the shops.

He thought of \(n-1\) positive integers \(a_1,...,a_n\) where for every \(i (1 \leq i \leq n-1)\) the condition \(1 \leq a_i \leq n-1\) holds.

Then, he made \(n-1\) tunnels numbered from \(1\) to \(n-1\). The \(i\)-th tunnel connects shop \(i\) and shop \((i+a_i)\). To keep the 'flow' of the shopping mall, constant one cannot travel backwards through a tunnel, only forwards. Trivially, since \(1 \leq a_i \leq n-1\) one cannot leave the mall once entering, genius!

At this point I should reveal I am stuck in this forsaken mall at cell \(1\) and want to go to cell \(t\) (they're having a really good sale). However, I don't know if I can get there, can you help me determine if I can reach cell \(t\) using the tunnel system?

Input Specification

Two lines. The first line contains two space-separated integers \(n (3 \leq n \leq 3 \times 10^4)\) and \(t (2\leq t \leq n)\); the number of shops and the index of the shop I want to get to.

The second line contains \(n-1\) space-separated integers \(a_1,...,a_{n-1} (1\leq a_i \leq n-1)\).

One is also guaranteed that using the tunnels, it is impossible to leave the shopping mall.

Output Specification

If I can get to the shop \(t\) using the tunnels print "YES". Otherwise, print "NO".

Sample Input 1

6 4
1 2 1 2 1 2

Sample Output 1


Sample Input 2

8 5
1 2 1 2 1 1 1

Sample Output 2



In the first example, we visit the shops \(1,2,4\); so we can reach shop \(4\).

In the second example, we can only visit shops \(1,2,4,6,7,8\); so wee cannot visit shop \(5\).


There are no comments at the moment.