Blast Damage
플래티넘 II의견: 0
Bessie is playing a video game where she needs to defeat a line of \(N\) enemies
with initial HPs given by the list \(v_1\dots v_N\)
(\(1\le N\le 2\cdot 10^5, 0\le v_i\le 10^9\)). In one attack, she can perform the
following sequence of steps:
- Choose \(i\) such that the \(i\)th enemy is still alive (that is, \(v_i>0\)).
- Deal one damage to the \(i\)th enemy and all enemies adjacent to it that are still alive. Specifically, for each \(j\in [\max(i-1, 1), \min(i+1, N)]\), if \(v_j>0\), subtract one from \(v_j\).
Help Bessie determine the minimum number of attacks she needs to defeat all
enemies (that is, reduce all \(v_i\) to 0).
Additionally, you are given a parameter \(M\) (\(0\le M\le 2\)). If \(M>0\), please
output a construction achieving the minimum number of attacks with a small
number of runs, where a run consists of attacking the same enemy consecutively.
Let \(R\) be the number of runs in your construction. Your construction should be
in the following format: output \(R\) on its own line, followed by \(R\) lines each
containing two integers \(i\) and \(r\) (\(1\le i\le N, 0\le r\le 10^9\)), meaning
that Bessie attacks the \(i\)-th enemy \(r\) times consecutively.
Depending on the value of \(M\), \(R\) must satisfy one of the following
constraints:
- \(M=1\): \(R\le 2N\) (it can be proven that a construction always exists).
- \(M=2\): \(R\le f(N)\), where \(f(N)\) is the maximum minimum number of runs over all lists of length \(N\).
Problem credits: Benjamin Qi
SCORING
- Inputs 4-7: \(M=0\)
- Inputs 8-11: \(M=1\)
- Input 12-13: \(M=2\)
Problem credits: Benjamin Qi
Each input consists of \(T\) (\(1\le T\le 10^5\)) independent tests. The first line
contains \(T\) and \(M\).
Each test is specified as follows:
The first line contains \(N\).
The second line contains \(v_1\dots v_N\).
It is guaranteed that the sum of \(N\) over all tests does not exceed \(10^6\).
For each test, output the minimum number of attacks on the first line.
Then if \(M>0\), output \(R+1\) additional lines as specified above. Any valid
construction will be accepted.
2 0
1
10
3
6 1 710
12For the second test, you can first perform one attack on the middle enemy. Then,
in any order after that, perform five attacks on the first enemy and six attacks
on the last enemy.
2 1
1
10
3
6 1 710
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4This output receives credit because \(R=2\le 2\) for test 1 and \(R=4\le 6\) for test 2.
2 2
1
10
3
6 1 710
1
1 10
12
3
2 1
3 6
1 5This output receives credit because \(R=1\le f(1)\) for test 1 and \(R=3\le f(3)\)
for test 2.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Platinum
평가 및 의견
Blast Damage
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Blast Damage