2037: [USACO 2025 January Contest, Platinum] Problem 2. Shock Wave
题目描述
Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has () tiles lined up in front of her, which require powers of at least to break, respectively ().
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 once, where is an integer in , it applies power to tile for all integers in the range . This power is also cumulative, so applying power twice to a tile will apply a total of power to the tile.
Please determine the fewest number of punches required to break all the tiles.
输入
The first line contains () representing the number of test cases.
Line contains a single integer , the number of tiles in test case .
Line contains space separated numbers representing that tile takes power to be broken.
It is guaranteed that the sum of all in a single input does not exceed .
输出
样例输入
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 1000000000000000000样例输出
2
3
2
4
4
2000000000000000000提示
For the first test, the only way for Bessie to break all the tiles with two punches is to punch twice, applying total powers of respectively.
For the second test, one way for Bessie to break all the tiles with three punches is to punch , , and one time each, applying total powers of respectively.
For the third test, one way for Bessie to break all the tiles with two punches is to punch and one time each, applying total powers of respectively.
SCORING:
- Input 2: All are equal.
- Inputs 3-6:
- Inputs 7-14: No additional constraints.