← 返回题目列表

AtCoder · agc057_b

B. 2A加x

中文机器翻译题面 查看原题

分数: 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