B - 2A + x Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 700

問題文

正整数列 A = (A_1, A_2, \ldots, A_N) および正整数 X が与えられます。あなたはこの数列に対して、次の操作を何度でも行うことができます(0 回でもよい):

  • 添字 i1\leq i\leq N)および、0\leq x\leq X となる非負整数 x を選ぶ。A_i2A_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

A_i2A_i+x に変更する操作を (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

Score : 700 points

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of positive integers and a positive integer X. You can perform the operation below any number of times, possibly zero:

  • Choose an index i (1\leq i\leq N) and a non-negative integer x such that 0\leq x\leq X. Change A_i to 2A_i+x.

Find the smallest possible value of \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} after your operations.

Constraints

  • 2\leq N\leq 10^5
  • 1\leq X\leq 10^9
  • 1\leq A_i\leq 10^9

Input

Input is given from Standard Input in the following format:

N X
A_1 A_2 \ldots A_N

Output

Print the smallest possible value of \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} after your operations.


Sample Input 1

4 2
5 8 12 20

Sample Output 1

6

Let (i, x) denote an operation that changes A_i to 2A_i+x. An optimal sequence of operations is

  • (1,0), (1,1), (2,2), (3,0)

which yields A = (21, 18, 24, 20), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 6.


Sample Input 2

4 5
24 25 26 27

Sample Output 2

0

An optimal sequence of operations is

  • (1,5), (1,5), (2,5), (2,1), (3,2), (3,3), (4,0), (4,3)

which yields A = (111,111,111,111), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 0.


Sample Input 3

4 1
24 25 26 27

Sample Output 3

3

Performing no operations achieves \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 3.


Sample Input 4

10 5
39 23 3 7 16 19 40 16 33 6

Sample Output 4

13