#CF4057. 好钥匙坏钥匙
好钥匙坏钥匙
题目描述
有 个箱子。第 个箱子里有 硬币。你需要打开所有 个箱子,从箱子 到箱子 。
有两种类型的钥匙可以用来打开箱子:
- 一把好钥匙,要花 个硬币;
- 一把坏钥匙,不需要任何硬币,但会将每个未打开的箱子中的所有硬币减半,包括即将打开的箱子。减半操作将向下取整。换句话说,用一把坏钥匙打开箱子 ,将会造成 $a_i=\lfloor \frac{x_i}2 \rfloor,a_{i+1}=\lfloor \frac{x_{i+1}}2 \rfloor,…,a_n=\lfloor \frac{x_n}2 \rfloor $。
- 任何钥匙(好的和坏的)在使用后都会断开,也就是说,它是一次性使用。
你需要总共使用 把钥匙,每个宝箱一个。最初,你没有硬币和钥匙。如果你想用一把好钥匙,那么你需要使用硬币购买。
并且在此过程中,你允许赊账;例如,如果你有 个硬币,你可以购买一把价值 个硬币的好钥匙,你的余额将变成 个硬币。
现在,求出按照从 号箱子到 号箱子的顺序打开所有 个箱子后,你能拥有的最大硬币数量。
输入格式
第一行包含单个整数 代表测试用例数。
每个测试用例的第一行包含两个整数 和 ,分别是箱子的数量和一把好钥匙的价格。
每个测试用例的第二行包含 个整数 代表每个箱子中的硬币数量。
所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一个整数,代表依次从 到 打开箱子后可以获得的最大硬币数量。
请注意,某些测试用例的答案可能超过 位整数类型,因此您应该在编程语言中至少使用 位整数类型。
测试样例
5
4 5
10 10 3 1
1 2
1
3 12
10 10 29
12 51
5 74 89 45 18 69 67 67 11 96 23 59
2 57
85 60
11
0
13
60
58
样例说明
在第一个测试案例中,一种可能的策略如下:
用 个硬币买一把好钥匙,打开箱子 ,收到 个硬币。您当前的余额为 个硬币。
用 枚硬币买一把好钥匙,打开 号箱子,收到 枚硬币。您当前的余额为 个硬币。
使用坏钥匙打开箱子 。由于使用了坏钥匙,箱子 中的硬币数量变为 ,箱子 中的硬币数变为 。您当前的余额为 。
使用坏钥匙打开箱子 。由于使用了坏钥匙,箱子 中的硬币数量变为 。您当前的余额为 。
在这个过程的最后,你有 个硬币,这可以被证明是最大的。