## Mock CCC '19 Contest 1 J5 - One-way Hopscotch

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You are playing hopscotch on a one-indexed array $$a$$ of $$N$$ integers. You can choose to start at some index $$j$$ (which is undecided). Your goal is to reach index $$N$$. This game of hopscotch is strange. At index $$i$$, it is already defined where you must hop to. At index $$i$$, you must hop to index $$i + a_i$$.

You want to find out, for how many starting indices $$j\ (1 \le j \le N)$$ will you be able to reach index $$N$$?

#### Input Specification

The first line will contain the integer $$N\ (1 \le N \le 10^5)$$, the number of elements.

The second line will contain $$N$$ integers, $$a_1, a_2, \ldots, a_N\ (1 \le a_i \le 10^3)$$.

#### Output Specification

Output the number of starting indices $$j\ (1 \le j \le N)$$ where you will be able to reach index $$N$$.

For 3/15 of the points, $$N \le 10^3, a_i \le 10$$.

For an additional 4/15 of the points, $$a_i \le 10$$.

#### Sample Input

6
5 2 2 2 3 1

#### Sample Output

4

#### Explanation For Sample

You will be able to reach index $$N=6$$ when starting at indices $$1, 2, 4,$$ or $$6$$.