Shock Wave
Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has N (2≤N≤105) tiles lined up in front of her, which require powers of at least p0,p1,…,pN−1 to break, respectively (0≤pi≤1018).
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.
For 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.
SCORING:
- Input 2: All pi are equal.
- Inputs 3-6: N≤100
- Inputs 7-14: No additional constraints.
Problem credits: Suhas Nagar
Source: USA Computing Olympiad.
Input Format
The first line contains T (1≤T≤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 p0,p1,…,pN−1 representing that tile i takes pi power to be broken.
It is guaranteed that the sum of all N in a single input does not exceed 5⋅105.
Output Format
T lines, the ith line representing the answer to the ith test case.