Shock Wave
다이아몬드 III의견: 0
Bessie is experimenting with a powerful hoof implant that has the ability to
create massive shock waves. She has \(N\) (\(2 \leq N \leq 10^5\)) tiles lined up in
front of her, which require powers of at least \(p_0,p_1,\dots,p_{N-1}\) to break,
respectively
(\(0 \leq p_i \leq 10^{18}\)).
Bessie can apply power by punching a specific tile but due to the strange nature
of her implant, it will not apply any power to the tile she punches. Instead, if
she chooses to punch tile \(x\) once, where \(x\) is an integer in \([0,N-1]\),
it applies \(|i-x|\) power to tile \(i\) for all integers \(i\) in the range
\([0,N-1]\). This power is also cumulative, so applying \(2\) power twice to a tile
will apply a total of \(4\) power to the tile.
Please determine the fewest number of punches required to break all the tiles.
Problem credits: Suhas Nagar
SCORING
- Input 2: All \(p_i\) are equal.
- Inputs 3-6: \(N\le 100\)
- Inputs 7-14: No additional constraints.
Problem credits: Suhas Nagar
The first line contains \(T\) (\(1 \leq T \leq 100\)) representing the number of
test cases.
Line \(2t\) contains a single integer \(N\), the number of tiles in test case \(t\).
Line \(2t+1\) contains \(N\) space separated numbers \(p_0,p_1, \ldots, p_{N-1}\) representing
that tile \(i\) takes \(p_i\) power to be broken.
It is guaranteed that the sum of all \(N\) in a single input does not exceed
\(5\cdot 10^5\).
\(T\) lines, the \(i\)th line representing the answer to the \(i\)th test case.
6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 10000000000000000002
3
2
4
4
2000000000000000000For the first test, the only way for Bessie to break all the tiles with two
punches is to punch \(0\) twice, applying total powers of \([0,2,4,6,8]\)
respectively.
For the second test, one way for Bessie to break all the tiles with three
punches is to punch \(0\), \(2\), and \(4\) one time each, applying total powers of
\([6,5,4,5,6]\) respectively.
For the third test, one way for Bessie to break all the tiles with two punches
is to punch \(0\) and \(1\) one time each, applying total powers of \([1,1,3,5,7]\)
respectively.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > January > Platinum
평가 및 의견
Shock Wave
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Shock Wave