Cannonball
실버 II의견: 0
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.
Problem credits: Suhas Nagar
SCORING
- Inputs 3-5: \(N \le 100\)
- Inputs 6-10: \(N \le 1000\)
- Inputs 11-20: No additional constraints.
Problem credits: Suhas Nagar
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\).
Output one number representing the number of targets that will be broken.
5 2
0 1
1 1
1 2
0 1
1 11Bessie 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 13The 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.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Bronze
평가 및 의견
Cannonball
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cannonball