AtCoder Grand Contest 057
翻译中…
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.
翻译中…
样例
Input #1
4 2
5 8 12 20
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$.
Input #2
4 5
24 25 26 27
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$.
Input #3
4 1
24 25 26 27
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$.
Input #4
10 5
39 23 3 7 16 19 40 16 33 6
Output #4
13
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。