分数: 700 点
问题陈述
给你一个序列 A = (A_1, A_2, \ldots, A_N) 的正整数和正整数 X。 您可以执行以下操作任意次数,可能为零:
- 选择索引 i (1\leq i\leq N) 和一个非负整数 x 这样 0\leq x\leq X。改变 A_i to 2A_i+x.
找到最小可能值 \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} 操作后。
约束
- 2\leq N\leq 10^5
- 1\leq X\leq 10^9
- 1\leq A_i\leq 10^9
输入
输入由标准输入按以下格式给出:
N X A_1 A_2 \ldots A_N
输出
打印以下的最小可能值 \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} 操作后。
示例输入 1
4 2 5 8 12 20
示例输出 1
6
让 (i, x) 表示改变的操作 A_i to 2A_i+x。最佳操作顺序是
- (1,0), (1,1), (2,2), (3,0)
产生 A = (21, 18, 24, 20),实现 \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 6.
示例输入 2
4 5 24 25 26 27
示例输出 2
0
最佳操作顺序是
- (1,5), (1,5), (2,5), (2,1), (3,2), (3,3), (4,0), (4,3)
产生 A = (111,111,111,111),实现 \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 0.
示例输入 3
4 1 24 25 26 27
示例输出 3
3
不执行任何操作即可实现 \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 3.
示例输入 4
10 5 39 23 3 7 16 19 40 16 33 6
示例输出 4
13