题目描述
给定一个非负整数 x,你要经过若干次以下操作将其变成 y,求最小代价:
- 选择一个 0≤i≤k,花费 ai 代价将 x 加或减 2i。
注意:你在操作时不需要保证 x 为非负整数。
输入格式
本题有多组测试数据。
第一行,一个正整数 T,表示测试数据组数。对于每组测试数据:
- 第一行,三个非负整数 x,y,k。
- 第二行,k+1 个正整数 a0,…,ak。
输出格式
对于每组测试数据,一行,一个非负整数,表示最小代价。
5
2 4 1
2 5
2 5 2
2 5 2
3 9 2
1 2 3
4 23 3
1 5 2 4
1 114 5
1 4 1 9 19 8
4
4
5
11
29
提示
【样例解释】
对于样例的第二组测试数据:经过以下两次操作即可让 x 变为 y,且代价最小:
- 取 i=2,令 x←x+22,此时 x=6,总代价为 2;
- 取 i=0,令 x←x−20,此时 x=5,总代价为 4。
【数据范围】
本题使用捆绑测试。
子任务编号 |
分值 |
T≤ |
x,y< |
k≤ |
ai |
1 |
6 |
103 |
23 |
3 |
≤109 |
2 |
15 |
210 |
10 |
3 |
21 |
2×105 |
230 |
1 |
4 |
27 |
30 |
≤2 |
5 |
20 |
104 |
≤109 |
6 |
11 |
2×105 |
对于所有数据:1≤T≤2×105,0≤x,y<230,1≤k≤30,1≤ai≤109。
【提示】
请使用较快的读入方式。