#PU1477. USACO 2025 January Contest, Platinum — Problem 2. Shock Wave
USACO 2025 January Contest, Platinum — Problem 2. Shock Wave
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 .
输出格式
lines, the th line representing the answer to the th test case.
数据范围
(见题面原文)
样例
样例 1
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 $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.