No.2821 A[i] ← 2A[j] - A[i]
タグ : / 解いたユーザー数 67
作問者 :
🦠みどりむし
/ テスター :
achapi
FplusFplusF
viral8
👑 
AngrySadEight
問題文
$N$ 個の整数 $A_1, A_2, \dots, A_N$ があります。
$N$ 個の互いに独立した問題 $1\text{-gathering}, 2\text{-gathering}, \dots, N\text{-gathering}$ を解いてください：
$k\text{-gathering}$
長さ $k$ の整数列 $B = (B_1, B_2, \dots, B_k)$ があり、はじめ $B = (A_1, A_2, \dots, A_k)$ が満たされています。
次の操作を $0$ 回以上何度でも行えます：
- $1 \leq i, j \leq k$ なる $2$ 整数 $i, j$ を自由に選び、$\large B_i$ を $\large 2B_j - B_i$ の値で置き換える。
操作を適切に行って得られる $V_k \coloneqq \displaystyle \max B - \min B$ の最小値 $V'_k$ を求めてください。
なお、これは必ず存在します。
入力
入力は、以下の形式で標準入力より与えられる：
$N$ $A_1 \enspace A_2 \enspace \dots \enspace A_N$
出力
各 $V'_1, V'_2, \dots, V'_N$ の値を、以下の形式で標準出力へ出力せよ：
$V'_1$ $V'_2$ $\vdots$ $V'_N$
制約
- $1 \leq N \leq 3 \times 10^5$
- $\left| A_i \right| < 2^{60} \scriptsize \; (1 \leq i \leq N)$
- 入力はすべて整数
サンプル
入出力例1
入力
4 2 6 5 -4
出力
0 4 1 1
たとえば、問題 $3\text{-gathering}$ について、次のように操作を行うことで $V_3 = 1$ を達成できます：
- はじめ、$B = (2, 6, 5)$ である。
- $(i, j) = (2, 3)$ として操作を行う。
- $B = (2, 4, 5)$ となる。
- $(i, j) = (3, 2)$ として操作を行う。
- $B = (2, 4, 3)$ となる。
- $(i, j) = (1, 3)$ として操作を行う。
- $B = (4, 4, 3)$ となる。
- このとき $\max B - \min B = 4 - 3 = 1$ である。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。