| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 653 | 206 | 175 | 33.144% |
Bessie has mastered the art of turning into a cannonball and bouncing along a number line of length $N$ $(1 \leq N \leq 10^5)$ with locations numbered 1,2,ドル\dots,N$ from left to right. She starts at some integer location $S$ $(1 \leq S \leq N)$ bouncing to the right with a starting power of 1ドル$. If Bessie has power $k,ドル her next bounce will be at a distance $k$ forward from her current location.
Every integer location from 1ドル$ to $N$ is either a target or a jump pad. Each target and jump pad has an integer value in the range 0ドル$ to $N$ inclusive. A jump pad with a value of $v$ increases Bessie's power by $v$ and reverses her direction. A target with a value of $v$ will be broken if landed on with a power of at least $v$. Landing on a target does not change Bessie's power or direction. A target that is broken will remain broken and Bessie can still bounce on it, also without changing power or direction.
If Bessie bounces for an infinite amount of time or until she leaves the number line, how many targets will she break?
If Bessie starts on a target that she can break, she will immediately do so. Similarly, if Bessie starts on a jump pad, the pad's effects will be applied before her first jump.
The first line of the input contains $N$ and $S,ドル where $N$ is the length of the number line and $S$ is Bessie's starting location.
The next $N$ lines describe each of the locations. The $i$th of these lines contains integers $q_i$ and $v_i,ドル where $q_i = 0$ if location $i$ is a jump pad and $q_i = 1$ if location $i$ is a target, and where $v_i$ is the value of location $i$.
5 2 0 1 1 1 1 2 0 1 1 1
1
Bessie starts at coordinate 2ドル,ドル which is a target of value 1ドル,ドル so she immediately breaks it. She then bounces to coordinate 3ドル,ドル which is a target of value 2ドル,ドル so she can't break it. She continues to coordinate 4ドル,ドル which switches her direction and increases her power by 1ドル$ to 2ドル$. She bounces back to coordinate 2ドル,ドル which is an already broken target, so she continues. At this point, she bounces to coordinate 0ドル,ドル so she stops. She breaks exactly one target at located at 2ドル$.
6 4 0 3 1 1 1 2 1 1 0 1 1 1
3
The path Bessie takes is 4ドル\to 5\to 3\to 1\to 6,ドル where the next bounce would take her out of the number line (11ドル$). She breaks targets 4,ドル 3, 6$ in that order.