#PU1372. USACO 2024 January Contest, Bronze — Problem 2. Cannonball

USACO 2024 January Contest, Bronze — Problem 2. Cannonball

USACO 2024 January Contest, Bronze — Problem 2. Cannonball

题目描述

Bessie has mastered the art of turning into a cannonball and bouncing along a number line of length NN (1≤N≤105)(1 \leq N \leq 10^5) with locations numbered 1,2,…,N1,2,\dots,N from left to right. She starts at some integer location SS (1≤S≤N)(1 \leq S \leq N) bouncing to the right with a starting power of 11. If Bessie has power kk, her next bounce will be at a distance kk forward from her current location. Every integer location from 11 to NN is either a target or a jump pad. Each target and jump pad has an integer value in the range 00 to NN inclusive. A jump pad with a value of vv increases Bessie's power by vv and reverses her direction. A target with a value of vv will be broken if landed on with a power of at least vv. 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 NN and SS, where NN is the length of the number line and SS is Bessie's starting location. The next NN lines describe each of the locations. The iith of these lines contains integers qiq_i and viv_i, where qi=0q_i = 0 if location ii is a jump pad and qi=1q_i = 1 if location ii is a target, and where viv_i is the value of location ii.

输出格式

(见题面原文)

数据范围

Inputs 3-5: N≤100N \le 100 Inputs 6-10: N≤1000N \le 1000 Inputs 11-20: No additional constraints. Problem credits: Suhas Nagar

样例

样例 1

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$.

样例 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.